2
$\begingroup$

i want to prove $x^a \equiv x^{a\,\bmod\,8} \pmod{15}$.....(1) my logic:

here, since $\mathrm{gcd}(x,15)=1$, and $15$ has prime factors $3$ and $5$ (given) we can apply Euler's theorem.

we know that $a= rem + 8q$, where $8= \phi(15)$,

$x^a \equiv x^{rem}. (x^8)^q \pmod{15}$......(2)

applying Euler's theorem we get:

$x^a \equiv x^{rem} \pmod{15}$......(3)

Is this proof correct or should I end up in getting $x^a \equiv x^a \pmod {15}$...(4)

  • 1
    I'm not 100% sure this is what you meant but the formatting was unreadable so I corrected it. Please make sure I typed what you meant.2012-12-06
  • 1
    You seem to assume that $x$ is relatively prime to $m$, but you do not state so; you should announce **all your assumptions** or otherwise people will be unable to help, or just give an example showing your claim is false.2012-12-06

2 Answers 2