Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.