

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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)

share|cite|improve this question
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. – Patrick Da Silva Dec 6 '12 at 8:04
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. – Marc van Leeuwen Dec 6 '12 at 9:30

Assuming you meant to add the hypothesis that $x$ is relatively prime to $m$, this is indeed immediate from Euler's theorem (stating $x^{\phi(m)}\equiv1\pmod m$ when $\gcd(x,m)=1$). One has $a=\phi(m)q+a\bmod\phi(m)$ for some integer $q$ and then $$ x^a=x^{\phi(m)q+a\bmod\phi(m)} =(x^{(\phi(m)})^qx^{a\,\bmod\,\phi(m)} \equiv1^qx^{a\,\bmod\,\phi(m)}=x^{a\,\bmod\,\phi(m)}\pmod m. $$

share|cite|improve this answer

If $b\equiv a\pmod m, b$ will be equal to $a\iff 0\le a<m$

For example, $m-2\equiv m-2\pmod m, 13\equiv 13\pmod {15}$

but, $m+2\equiv 2\pmod m, 17\equiv 2\pmod {15}$

If $b\equiv c\pmod{\phi(m)} ,$i.e., if $b=c+d\phi(m)$

$y^b=y^{c+d\phi(m)}=y^c\cdot(y^{\phi(m)})^d\equiv y^c \pmod m$ for $(y,m)=1$

Here $\phi(15)=\phi(3)\phi(5)=2\cdot4=8$

Observe that this condition is no way necessary as proved below.

If $y^b\equiv y^d\pmod m$ where $b\ge c$

$y^{b-d}\equiv1\pmod m\iff ord_my\mid (b-d)$ does not need to divide $\phi(m)$ unless $ord_my=\phi(m)$ where $y$ is a primitive root of $m$.

share|cite|improve this answer

Your Answer


