1
$\begingroup$

I am trying to show that $a^{12} \equiv 1 \mod 32760$ for each $a \in \mathbb{Z}$ coprime to $32760$. I have found the prime decomposition $32760 = 2^3 \cdot 3^3 \cdot 5 \cdot 7 \cdot 13$ and determined $\phi(32760)$, where $\phi$ is the Euler's totient function. This gives me that $\phi (32760) = 8640$.

Using Euler's congruence, this gives that $a^{8640} \equiv 1 \mod 32760$, but this is still far from the result I want to show... I also know a consequence of Eulers congruence, which states that $e \equiv e' \mod \phi (n)$ implies that $a^e \equiv a^{e'} \mod n$, but I do not see how to use this...

Any hints would be appreciated.

$\textbf{EDIT:}$ I made a mistake in my primefactorization, it is edited now.

$\endgroup$
4
  • 1
    $\begingroup$ $7^{12} \neq 1 \mod 32760$ $\endgroup$
    – Leox
    Feb 16 '17 at 18:28
  • 1
    $\begingroup$ @Leox, $\gcd(7, 32760) \ne 1$. $\endgroup$
    – lhf
    Feb 16 '17 at 18:29
  • 2
    $\begingroup$ Your prime factorization is incorrect. $32760 = 2^3 \cdot 3^2 \cdot 5\cdot 7\cdot 13$ $\endgroup$
    – Doug M
    Feb 16 '17 at 18:31
  • 1
    $\begingroup$ @lhf yes, just his factorisation was wrong $\endgroup$
    – Leox
    Feb 16 '17 at 18:36
4
$\begingroup$

For each maximal prime power $\,p^{\large k}$ dividing $\, 32760 = 2^{\large 3} \cdot 3^{\large 2} \cdot 5\cdot 7\cdot 13\,$ we have that Euler's $\,\phi = \phi(p^k)\mid 12,\ $ so $\,12 = \phi k,\,$ so $\ {\rm mod}\,\ p^{\large k}\!:\,\ a^{\large 12} \equiv (\color{#c00}{a^{\large \phi}})^{\large k}\equiv \color{#c00}1^{\large k}\equiv 1\, $ by $\rm\color{#c00}{Euler's}$ Theorem.

Thus, since all $\,p^{\large k}$ divide $\, a^{\large 12}\!-1,\,$ so too does their lcm = product $= 32760$

Remark $\ $ See Carmichael's Lambda Theorem for the general result.

$\endgroup$
4
$\begingroup$

We have $$32760 = 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 13$$ By the Chinese remainder theorem, $$U(32760) \cong U(8) \times U(9) \times U(5) \times U(7) \times U(13) \cong C_2 \times C_2 \times C_6 \times C_4 \times C_6 \times C_{12}$$ which has exponent $12$.

In terms of congruences, by Euler–Fermat we have

$\quad a^2 \equiv 1 \bmod 8$

$\quad a^6 \equiv 1 \bmod 9$

$\quad a^4 \equiv 1 \bmod 5$

$\quad a^6 \equiv 1 \bmod 7$

$\quad a^{12} \equiv 1 \bmod 13$

and so $a^{12} \equiv 1 \bmod 8,9,5,7,13$

By the Chinese remainder theorem,

$\quad a^{12} \equiv 1 \bmod 32760 $

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