5
$\begingroup$

For any integer $a$, $a^{37} \equiv a \left( \text{mod } 1729\right).$

We're asked to use Euler's Theorem to prove this.

What I've tried:

$\phi(1729)=\phi(7)\phi(13)\phi(19)=1296$.

If $(a,n)=1$ then $a^{1296} \equiv 1 \left( \text{mod } 1729\right)$. I note that $1296=36^2$ and that something equivalent to what I need to prove is $$a(a^{36}-1)\equiv 0 \left( \text{mod } 1729\right).$$

I am now wondering what are the conditions for $a^n \equiv b^n \left( \text{mod } m\right)$ implying $a \equiv b \left( \text{mod } m\right)$ so then I can say $(a^{36})^{36} \equiv 1 (\text{mod } 1729)$ implies $a^{36} \equiv 1 (\text{mod }1729)$ at which point the equivalent statement would be true.

$\endgroup$
2
$\begingroup$

It is not much more work (and more insightful) to prove the general case, a variant of which characterizes Carmichael numbers (composites that behave like primes do in little Fermat).

Theorem $ $ (Korselt's Pseudoprime Criterion) $\ $ For $\rm\:1 < e,n\in \Bbb N\:$ we have

$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\ n\ \ is\ \ squarefree,\ \ and \ \ p\!-\!1\mid e\!-\!1\ \, for\ all \ primes\ \ p\mid n$$

Proof $\ \ (\Leftarrow)\ \ $ Since a squarefree natural divides another iff all its prime factors do, we need only show $\rm\: p\mid a^e\!-\!a\:$ for each prime $\rm\:p\mid n,\:$ i.e. that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1}\equiv 1\ \ ( mod\ p),\:$ which, since $\rm\:p\!-\!1\mid e\!-1,\:$ follows from $\rm\:a \not\equiv 0\:\Rightarrow\: a^{p-1} \equiv 1\ \ ( mod\ p),\:$ by little Fermat.

$(\Rightarrow)\ \ $ Given that $\rm\: n\mid a^e\!-\!a\:$ for all $\rm\:a\in\Bbb Z,\:$ we must show

$$\rm (1)\ \ n\,\ is\ squarefree,\quad and\quad (2)\ \ p\mid n\:\Rightarrow\: p\!-\!1\mid e\!-\!1$$

$(1)\ \ $ If $\rm\,n\,$ isn't squarefree then $\rm\,1\neq a^2\!\mid n\mid a^e\!-\!a \Rightarrow\: a^2\mid a\:\Rightarrow\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: a^2\mid a^e)$

$(2)\ \ $ Let $\rm\ a\ $ be a generator of the multiplicative group of $\rm\:\Bbb Z/p.\:$ Thus $\rm\ a\ $ has order $\rm\:p\!-\!1.\:$ Now $\rm\:p\mid n\mid a\,(a^{e-1}\!-\!1)\:$ but $\rm\:p\nmid a,\:$ so $\rm\: a^{e-1}\!\equiv 1\,\ ( mod\ p),\:$ therefore $\rm\:e\!-\!1\:$ must be divisible by $\rm\:p\!-\!1,\:$ the order of $\rm\,\ a\,\ (mod\ p).\quad$ QED

$\endgroup$
  • $\begingroup$ Thank you very much, I like this. If I can find a proof using Euler's theorem I could come back and submit that as well. $\endgroup$ – Frudrururu Mar 25 '13 at 2:17
6
$\begingroup$

I think it's better to think about this problem using the Chinese remainder theorem. That is, since we have the ring isomorphism $\mathbb{Z}/1729 \cong \mathbb{Z}/7 \times \mathbb{Z}/13 \times\mathbb{Z}/19$, via the map $m \mapsto (m \ \mathrm{mod} \ 7, \ m \ \mathrm{mod} \ 13, \ m \ \mathrm{mod} \ 19)$, it is enough to verify that $a^{37}=a \ \mathrm{mod} \ x$ where $x$ is any one of $7,13$ and $19$. But this follows from Fermat's little theorem.

$\endgroup$
  • $\begingroup$ I just realized this basically proves the $lcm$ portion of my answer. Nice insight! $\endgroup$ – Display name Feb 23 '18 at 21:01
0
$\begingroup$

Fermat's Little Theorem is weak. No wonder it's called "little". Euler's Theorem is also pathetic. What you gotta use is Carmichael's Theorem. It states that if $(a,n)=1$, then $a^{\lambda(n)} \equiv 1 \mod n$. To calculate $\lambda(n)$, let the prime factorization of $n$ be $\prod p_i^{a_i}.$ Then we have $$\lambda(n)=lcm[\lambda(p_1^{a_1}),\lambda(p_2^{a_2})...\lambda(p_k^{a_k})]$$

It may help to know that for $p>2$, $k \ge 0$, we have $\lambda(p^k)=\phi(p^k)$.

Furthermore, $\lambda(2^n)=a\phi(2^n)$ where $a=1$ if $n \le 2$ and $a=0.5$ otherwise.

We compute $\lambda(1729)= lcm[\lambda(7),\lambda(13),\lambda(19)]=lcm(6,12,18)=36$ and the result follows.

As an added bonus, you cannot get any better than this. $\lambda(n)$ is the lowest number such that $\forall (a,n)=1, \ a^{\lambda(n)} \equiv 1 \mod n$

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