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 following statement :

If $p$ is a prime number greater than $3$ and $\gcd(a,24\cdot p)=1$ then :

$a^{p-1} \equiv 1 \pmod {24\cdot p}$

Here is my attempt :

The Euler's totient function can be written in the form :

$n=p_1^{k_1}\cdot p_2^{k_2} \ldots \cdot p_r^{k_r} \Rightarrow \phi(n)=p_1^{k_1}\cdot\left(1-\frac{1}{p_1}\right)\cdot p_2^{k_2}\cdot\left(1-\frac{1}{p_2}\right)\ldots p_r^{k_r}\cdot \left(1-\frac{1}{p_r}\right)$

So,

$\phi(24 \cdot p)=2^3\cdot \left(1-\frac{1}{2}\right)\cdot3^1\cdot\left(1-\frac{1}{3}\right)\cdot p\cdot\left(1-\frac{1}{p}\right)=8\cdot(p-1)$

Euler's totient theorem states that :

if $\gcd(a,n)=1$ then $a^{\phi(n)} \equiv 1 \pmod n$

Therefore we may write :

$a^{\phi(n)}-1 \equiv 0 \pmod n \Rightarrow a^{\phi(24\cdot p)}-1=a^{8\cdot(p-1)}-1 \equiv 0 \pmod{24\cdot p} \Rightarrow$

$\Rightarrow \left(a^{p-1}\right)^8-1=(a^{p-1}-1)\cdot \displaystyle \sum_{i=0}^7 a^{(p-1)\cdot i} \equiv 0\pmod{24\cdot p}$

So we may conclude :

$(a^{p-1}-1) \equiv 0 \pmod {24\cdot p}$ , or $\displaystyle \sum_{i=0}^7 a^{(p-1)\cdot i} \equiv 0\pmod{24\cdot p}$

How can I prove that $\displaystyle \sum_{i=0}^7 a^{(p-1)\cdot i} \not\equiv 0\pmod{24\cdot p}$ ?

share|improve this question
    
I think you need to prove more: you need to prove that $\gcd(\sum_{i=0}^7 a^{(p-1)*i},24 p) = 1$, otherwise $(a^{p-1}-1)\sum_{i=0}^7 a^{(p-1)*i} \equiv 0 \bmod 24p$ can be without $a^{p-1} \equiv 0 \bmod 24p$. –  KevinDL Dec 3 '11 at 11:31
add comment

3 Answers

up vote 4 down vote accepted

Hint: The claim follows from proving the following facts separately: $a^{p-1}\equiv 1\pmod 8$, $a^{p-1}\equiv 1\pmod 3$, and $a^{p-1}\equiv 1\pmod p$.

share|improve this answer
    
,Thanks for the hint. I proved $a^{p-1}\equiv 1\pmod 3$ , but I don't see how to prove $a^{p-1}\equiv 1\pmod 8$ –  pedja Dec 3 '11 at 12:30
2  
@pedja: $a$ is odd, and $p-1$ is even. How many cases you need to check, when working modulo $8$? Are you familiar with the structure of the multiplicatice group of residue classes modulo a prime power? IOW don't let the totient theorem hang you! –  Jyrki Lahtonen Dec 3 '11 at 12:39
add comment

HINT $\ $ By Carmichael's simple generalization of Euler $\phi$, since prime $\rm\:p\:$ is coprime to $2,3$

$\rm\ \ \lambda(8\cdot3\cdot p) = lcm(\lambda(8),\lambda(3),\lambda(p)) = lcm(\phi(8)/2,\phi(3),\phi(p)) = lcm(2,2,p-1) = p-1\ $

therefore $\rm\quad gcd(n,24\:p) = 1\ \ \Rightarrow\ \ 1\ \equiv\ n^{\:\lambda(24\:p)}\: \equiv \ n^{p-1}$

share|improve this answer
add comment

Since $(a,24\cdot p)=1$, it also follows that $(a,p)=(a,3)=(a,8)=1$.

By the generalization of Fermat's little theorem, $a^{p-1}\equiv 1\pmod{p}$, $a^2\equiv 1\pmod{3}$, and $a^4\equiv 1\pmod{8}$. But $a^4\equiv 1\pmod{8}$, implies $a\equiv 1,3,5,7\pmod{8}$, and in all cases $a^2\equiv 1\pmod{8}$.

Since $p-1$ is even, $a^{p-1}\equiv 1$ in all cases, since $a^{p-1}\equiv (a^2)^{(p-1)/2}\equiv 1^{(p-1)/2}\pmod{3,8}$.

Then $a^{p-1}-1$ is divisible by $3$, $8$, and $p$, and thus as a common multiple, is divisible by $\mathrm{lcm}(3,8,p)=24\cdot p$, so $a^{p-1}\equiv 1\pmod{24\cdot p}$.

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.