4
$\begingroup$

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}$ ?

  • 0
    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$.2011-12-03

3 Answers 3

5

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$.

  • 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!2011-12-03
4

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}$.

2

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}$