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.

For all integers $a$ prove that
$$a^7 \equiv a \pmod {42}.$$ There is no use telling you all what and how much I tried because I cannot even understand the problem itself left alone attempting it. It would be great help for me if I would be provided some hint on either solving the problem or understanding it.

But, I see one thing that $42=7\cdot6$ and somehow we can use Fermat theorem but how? I do not know it. All suggestions/advice leading me to the problem would be greatly welcomed.

share|improve this question

4 Answers 4

up vote 8 down vote accepted

You need to show that 42 always divides $a^7-a.$ Since $42 = 2\cdot 3 \cdot 7,$ it suffices to show that $2,3,7$ divide $a^7-a.$

  • 2 divides $a^7-a$ because $a^7$ has the same parity as $a.$
  • 3 divides $a^7-a = a(a^6-1) = a(a^3-1)(a^3+1)$ because $a^3 \equiv a \mod 3$ (we just check that by cases).
  • 7 divides $a^7-a$ by Fermat's little theorem.
share|improve this answer
    
thanks .got it. –  shrey Aug 23 '12 at 8:46
    
Isn't it easier to show $3$ by showing $$a^7-a = a(a^6-1)=a(a^2-1)(a^4+a^2+1) = (a^3-a)(a^4+a^2+1)$$ and it follows since $3|a^3-a$. –  Thomas Andrews Feb 11 '13 at 21:58
    
@ThomasAndrews You are probably right. Or perhaps even easier since we don't need to factorize, $a^7-a = a^3-a=0 \pmod 3$ by two applications of FLT. –  Ragib Zaman Feb 12 '13 at 13:23

Since $42 = 2\cdot 3 \cdot 7$, it suffices to prove:

$a^7 \equiv a$ (mod 2)

$a^7 \equiv a$ (mod 3)

$a^7 \equiv a$ (mod 7)

By Fermat's little theorem, $a^2 \equiv a$ (mod 2)

Hence $a^n \equiv a$ (mod 2) for all integer $n \ge 1$. In particular, $a^7 \equiv a$ (mod 2)

By Fermat's little theorem,

$a^3 \equiv a$ (mod 3)

Hence $a^6 \equiv a^2$ (mod 3)

Hence $a^7 \equiv a^3 \equiv a$ (mod 3)

By Fermat's little theorem,

$a^7 \equiv a$ (mod 7)

share|improve this answer

By Fermat's little theorem, $a^{p-1}≡1(mod\ p)$ for $(a,p)=1$ where any integer a, prime p.

So, $a^{A_p(p-1)}≡1(mod\ p)$ for any natural number $A_p$.

$=>a^{A_p(p-1)+1}≡a$ for $(a,p)=1$

If p|a, $p|a(a^{A_p(p-1)}-1)=>p|(a^{A_p(p-1)+1}-a)$

So in either cases, $p|(a^{A_p(p-1)+1}-a)$ for any integer a, prime p.

For $p=2,3,7,\ A_2+1=2A_3+1=6A_6+1$ So, $A_2=2A_3=6A_6$ and $A_3=3A_6$

So, $lcm(2,3,7)|(a^{6d+1}-a)$ for any integer $d,a$,

i.e., $42|(a^{6d+1}-a)$ for any integer $d,a$.

Here in this problem, d=1.

share|improve this answer

Hint $\ $ Applying the following simple generalization of the little Fermat-Euler theorems, since $\rm\:n = 42 = \color{#C00}2\cdot\color{#0A0}3\cdot\color{brown} 7,\:$ is squarefree, it suffices to check $\rm\:\color{#C00}1,\color{#0A0}2,\color{brown}6\:|\:7\!-\!1 = e\!-\!1.$

Theorem $\ $ For natural numbers $\rm\:a,e,n\:$ with $\rm\:e,n>1$

$\qquad\rm n\:|\:a^e-a\:$ for all $\rm\:a\:\iff n\:$ is squarefree, and prime $\rm\:p\:|\:n\:\Rightarrow\: p\!-\!1\:|\:e\!-\!1$

Proof $\ (\Leftarrow)\ \ $ Since a squarefree natural divides another iff all its prime factors do, we need only show $\rm\:p\:|\:a^e\!-\!a\:$ for each prime $\rm\:p\:|\:n,\:$ or, that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1} \equiv 1\pmod p,\:$ which, since $\rm\:p\!-\!1\:|\:e\!-\!1,\:$ follows from $\rm\:a \not\equiv 0\:$ $\Rightarrow$ $\rm\: a^{p-1} \equiv 1 \pmod p,\:$ by little Fermat.
$(\Rightarrow)\ \ $ See this answer

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.