a^37==a(mod 1729)

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

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

 

We're asked to use Euler's Theorem to prove this.
What I've tried:
ϕ(1729)=ϕ(7)ϕ(13)ϕ(19)=1296 $\varphi (1729)=\varphi (7)\varphi (13)\varphi (19)=1296$ .
If (a,n)=1 $(a,n)=1$ then a 1296 ≡1(mod 1729) $a^{1296}\equiv 1\left(\text{mod }1729\right)$ . I note that 1296=36 2  $1296={36}^2$ and that something equivalent to what I need to prove is

a(a 36 −1)≡0(mod 1729). $$a(a^{36}-1)\equiv 0\left(\text{mod }1729\right).$$

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

 

                    

3 Answers 3                

 

 $$

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 1<e,n∈N $1<\mathrm{e},\mathrm{n}\in \mathbb{N}$ we have

∀a∈Z: n∣a e −a ⟺ n  is  squarefree,  and  p−1∣e−1 for all primes  p∣n $$\mathrm{\forall }\mathrm{a}\in \mathbb{Z}:\mathrm{n}\mid {\mathrm{a}}^{\mathrm{e}}-\mathrm{a}⟺\mathrm{n}\mathrm{i}\mathrm{s}\mathrm{s}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{e},\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{p}-1\mid \mathrm{e}-1\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{s}\mathrm{p}\mid \mathrm{n}$$

Proof   (⇐)   $(\Leftarrow )$ Since a squarefree natural divides another iff all its prime factors do, we need only show p∣a e −a $\mathrm{p}\mid {\mathrm{a}}^{\mathrm{e}}-\mathrm{a}$ for each prime p∣n, $\mathrm{p}\mid \mathrm{n},$ i.e. that a≢0⇒a e−1 ≡1  (mod p), $\mathrm{a}\not\equiv 0\Rightarrow {\mathrm{a}}^{\mathrm{e}-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{p}),$ which, since p−1∣e−1, $\mathrm{p}-1\mid \mathrm{e}-1,$ follows from a≢0⇒a p−1 ≡1  (mod p), $\mathrm{a}\not\equiv 0\Rightarrow {\mathrm{a}}^{\mathrm{p}-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{p}),$ by little Fermat.
(⇒)   $(\Rightarrow )$ Given that n∣a e −a $\mathrm{n}\mid {\mathrm{a}}^{\mathrm{e}}-\mathrm{a}$ for all a∈Z, $\mathrm{a}\in \mathbb{Z},$ we must show

(1)  n is squarefree,and(2)  p∣n⇒p−1∣e−1 $$(1)\mathrm{n}\mathrm{i}\mathrm{s}\mathrm{s}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{e},\mathrm{a}\mathrm{n}\mathrm{d}(2)\mathrm{p}\mid \mathrm{n}\Rightarrow \mathrm{p}-1\mid \mathrm{e}-1$$

(1)   $(1)$ If n $\mathrm{n}$ isn't squarefree then 1≠a 2 ∣n∣a e −a⇒a 2 ∣a⇒⇐ $1\ne {\mathrm{a}}^2\mid \mathrm{n}\mid {\mathrm{a}}^{\mathrm{e}}-\mathrm{a}\Rightarrow {\mathrm{a}}^2\mid \mathrm{a}\Rightarrow \Leftarrow$ (note  e>1⇒a 2 ∣a e ) $(\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{e}>1\Rightarrow {\mathrm{a}}^2\mid {\mathrm{a}}^{\mathrm{e}})$
(2)   $(2)$ Let  a  $\mathrm{a}$ be a generator of the multiplicative group of Z/p. $\mathbb{Z}/\mathrm{p}.$ Thus  a  $\mathrm{a}$ has order p−1. $\mathrm{p}-1.$ Now p∣n∣a(a e−1 −1) $\mathrm{p}\mid \mathrm{n}\mid \mathrm{a}({\mathrm{a}}^{\mathrm{e}-1}-1)$ but p∤a, $\mathrm{p}\nmid \mathrm{a},$ so a e−1 ≡1 (mod p), ${\mathrm{a}}^{\mathrm{e}-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{p}),$ therefore e−1 $\mathrm{e}-1$ must be divisible by p−1, $\mathrm{p}-1,$ the order of  a (mod p). $\mathrm{a}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{p}).$ QED

 

       

•  $$ 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.  $$ – Frudrururu Mar 25 '13 at 2:17

 

                

 

 $$

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

 

 

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

        

 

                

 

 $$

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 $(a,n)=1$ , then a λ(n) ≡1modn $a^{\lambda (n)}\equiv 1\mathrm{mod}n$ . To calculate λ(n) $\lambda (n)$ , let the prime factorization of n $n$ be ∏p a i  i . $\prod p_i^{a_i}.$ Then we have

λ(n)=lcm[λ(p a 1  1 ),λ(p a 2  2 )...λ(p a k  k )] $$\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 $p>2$ , k≥0 $k\ge 0$ , we have λ(p k )=ϕ(p k ) $\lambda (p^k)=\varphi (p^k)$ .
Furthermore, λ(2 n )=aϕ(2 n ) $\lambda (2^n)=a\varphi (2^n)$ where a=1 $a=1$ if n≤2 $n\le 2$ and a=0.5 $a=0.5$ otherwise.
We compute λ(1729)=lcm[λ(7),λ(13),λ(19)]=lcm(6,12,18)=36 $\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. λ(n) $\lambda (n)$ is the lowest number such that ∀(a,n)=1, a λ(n) ≡1modn $\mathrm{\forall }(a,n)=1,a^{\lambda (n)}\equiv 1\mathrm{mod}n$