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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – KevinDL Dec 3 '11 at 11:31
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ,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$ $\endgroup$ – Peđa Terzić Dec 3 '11 at 12:30
  • 2
    $\begingroup$ @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! $\endgroup$ – Jyrki Lahtonen Dec 3 '11 at 12:39
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.