Prove that for all $x \in \mathbb{Z}_{1729}^{\times}$ holds $x^{1728} \equiv1 \pmod{1729}$

I do not know how to prove that for all $x \in \mathbb{Z}_{1729}^{\times}$ holds:

$$x^{1728} \equiv1 \pmod{1729}$$

From algebra I know that for any group $G$ and $g \in G$ holds

$$g^{|G|} = 1$$

and I think that this should help here too, but I do not know how I could use it here. Could you help me?

• Notably, this question asks you to prove that 1729 is a Carmichael number – Omnomnomnom Jun 18 '18 at 23:58
• This question can easily be answered using Euler's theorem. Note that $\varphi(1729)$ is the order of the group $\Bbb Z_{1729}^\times$ – Omnomnomnom Jun 19 '18 at 0:02
• @Omnomnomnom, not really in this case, because $\varphi(1729)= 1296$ does not divide $1728$. – lhf Jun 19 '18 at 1:19
• @lhf whoops! Good catch – Omnomnomnom Jun 19 '18 at 3:19

We have that $1729 = 7 \cdot 13 \cdot 19$. Now try working modulo these primes by using the Fermat's Little Theorem to deduce the result.

Here's how you can deal with the factor $19$. First note that $\gcd(1729,x) = 1 \implies \gcd(19,x) = 1$. Now by Fermat's Little Theorem we have that $x^{18} \equiv 1 \pmod{19}$. Now note that $18 \mid 1728$ and so we have that $x^{1728} \equiv 1 \pmod{19}$. Do the same for other primes.

• What if $\gcd(1729, x) \ne 1$. – fleablood Jun 19 '18 at 0:08
• @fleablood Then $x \not \in \mathbb{Z}_{1729}^{\times}$, right? – Stefan4024 Jun 19 '18 at 0:09
• Argh.... I saw $\mathbb Z^{\times}_{1729}$ and I thought $\mathbb Z^{+}_{1729}$. – fleablood Jun 19 '18 at 0:21

By the Chinese remainder theorem, $$\mathbb{Z}_{1729}^{\times} \cong \mathbb{Z}_{7}^{\times} \times \mathbb{Z}_{13}^{\times} \times \mathbb{Z}_{19}^{\times} \cong C_{6} \times C_{12} \times C_{18}$$ Therefore, $x^{36} \equiv 1 \bmod{1729}$ for all $x \in \mathbb{Z}_{1729}^{\times}$.

Since $1728$ is a multiple of $36$, we have $x^{1728} \equiv 1 \bmod{1729}$.

• – lhf Jun 19 '18 at 1:22