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.

How can you prove that:

$$a^7\equiv a\:(\text{mod } 42)$$

I haven't been given any other information other than to use Fermat's theorem.

share|improve this question
2  
"Use Fermat's theorem" is a pretty good hint. What are your thoughts on how to apply it? –  Qiaochu Yuan Nov 27 '12 at 1:45
3  
Work separately modulo $7$, $2$, and $3$. –  André Nicolas Nov 27 '12 at 2:03

5 Answers 5

Hint $\rm\,\ x\!-\!1\mid x^n\!-\!1\:\Rightarrow\:a^{p-1}\!-\!1\mid a^{n(p-1)}\!-\!1\:\Rightarrow\:p\mid a^p\!-\!a\mid a^{1+\color{#C00}{n(p-1)}}\!-\!a\,\ $ by little Fermat.

So if $\rm\:p_i\:$ are distinct primes then $\rm\ p_i\!-\!1\mid \color{#C00}{m\!-\!1}\:\Rightarrow\: p_1\cdots p_k\mid a^m - a$

share|improve this answer

There are two versions of Fermat's Theorem.

Version $1$: If $a$ is not divisible by $p$, then $a^{p-1}\equiv 1\pmod{p}$.

Version $2$: For any $a$, $a^p\equiv a\pmod p$.

The more common version is Version $1$. From it, you can easily deduce Version $2$. For if $a$ is not divisible by $p$, then $a^{p-1}\equiv 1\pmod{p}$. Multiplying by $a$, we get that $a^p\equiv a \pmod{p}$. On the other hand, if $a$ is divisible by $p$, we have that both $a^p$ and $a$ are congruent to $0$ modulo $p$, and therefore are congruent to each other.

We omit the proof that Version $2$ implies Version $1$. It is straightforward.

Using Version $2$, we find that for all $a$, $$a^7 \equiv a\pmod{7}.\tag{$1$}$$

Now work modulo $2$. It is hardly necessary to use machinery. If $a$ is odd, then so is $a^7$, and if $a$ is even, then so is $a^7$. We conclude that for all $a$, $$a^7 \equiv a\pmod{2}.\tag{$2$}$$

Now work modulo $3$. We can do a three-cases verification that $a^7\equiv a\pmod{3}$ for all $a$. Or else we can use Fermat's Theorem. If $a$ is divisible by $3$, then $a^7$ and $a$ are congruent to $0$ modulo $3$, so they are conruent to each other. If $a$ is not divisible by $3$, then $a^2\equiv 1\pmod{3}$, and therefore $a^6\equiv 1\pmod{3}$, and therefore $a^7\equiv a \pmod{3}$. we conclude that for all $a$ $$a^7 \equiv a\pmod{3}.\tag{$3$}$$

So $7$, $2$, and $3$ each divide $a^7-a$. Since they are pairwise relatively prime, it follows that their product $42$ divides $a^7-a$ for all $a$. This is what we wanted to prove.

share|improve this answer

Directly:

$$a^7=a\pmod{42}\Longleftrightarrow \,\,\exists \,k\in\Bbb Z\,\,\,s.t.\,\,\,a^7-a=42k\,\,,\,$$

But

$$(1)\;\;\;\;\text{If}\,a=0\pmod{42}\,\,,\,\text{ then the claim is obvious. Otherwise:}$$

$$a^7=a\pmod{42}\Longrightarrow a^6=1\pmod{42}\Longleftrightarrow \exists\,k\in\Bbb Z\,\,s.t.\,\,a^6-1=42k$$

But:

$$a^6-1=(a^3-1)(a^3+1)=(a-1)(a^2+a+1)(a+1)(a^2-a+1)$$

Now check all the cases and verify the above is always divisible by $\,2\,,\,3\,,\,and\,\,7\,$

share|improve this answer

Note first $42 = 2\cdot 3\cdot 7$.

By Fermat's theorem, $a^2 \equiv a$ (mod 2). Hence $a^3 \equiv a^2 \equiv a$ (mod $2$), etc. Hence $a^7 \equiv a$ (mod $2$).

By Fermat's theorem, $a^3 \equiv a$ (mod 3). Hence $a^7 = (a^3)^2a \equiv a^3 \equiv a$ (mod $3$).

By Fermat's theorem, $a^7 \equiv a$ (mod $7$).

Therefore $a^7 \equiv a$ (mod $42$).

share|improve this answer

Hint:

Use Fermat's Theorem and the Chinese Remainder Theorem.

share|improve this answer

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.