Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

2 Answers 2

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.