2
$\begingroup$

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?

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

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.

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

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

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