Question and Answers Forum

All Questions      Topic List

Number Theory Questions

Previous in All Question      Next in All Question      

Previous in Number Theory      Next in Number Theory      

Question Number 111704 by Aina Samuel Temidayo last updated on 04/Sep/20

Assuming FLT, prove Fermat−Euler theorem: (a,n) =1,n≥2⇒a^(∅(n)) ≡1(mod n)

$$\mathrm{Assuming}\:\mathrm{FLT},\:\mathrm{prove}\:\mathrm{Fermat}−\mathrm{Euler} \\ $$$$\mathrm{theorem}:\:\left(\mathrm{a},\mathrm{n}\right)\:=\mathrm{1},\mathrm{n}\geqslant\mathrm{2}\Rightarrow\mathrm{a}^{\emptyset\left(\mathrm{n}\right)} \equiv\mathrm{1}\left(\mathrm{mod}\right. \\ $$$$\left.\mathrm{n}\right) \\ $$

Answered by Aina Samuel Temidayo last updated on 04/Sep/20

Assuming FLT (a,n)=1,n≥2⇒a^(∅(n)) ≡1(mod n) If n is prime,then ∅(n) = n−1 and Euler′s theorem says a^(n−1) =1(mod n), which is Fermat′s theorem. Since n is prime, then all of the numbers {1,...,n−1} are relatively prime to n. ⇒ ∅(n)=n−1 Proof: Let ∅(n)=k, and let {a_1 ,a_2 ,...,a_k } be a residue system mod n. I may assume that the a_i ′s lie in the range {1,...,n−1} as a reduced residue system mod n is a set of numbers a_1 ,a_2 ,a_3 ,...,a_(∅(n)) such that: −if i≠j, then a_i ≠a_j (mod n). That is, the a′s are distinct mod n. −For each i, (a_i ,n)=1. That is, all the a′s are relatively prime to n. Since all a′s are relatively prime to n, then the assumption that the a_i ′s lie in the range {1,...,n−1} is correct. Since (a,n) =1, {aa_1 ,...,aa_k } is another reduced residue system mod n. Since this is the same set of numbers mod n as the original system, the two systems must have the same product mod n: ⇒ (aa_1 )(aa_2 )...(aa_k ) = a_1 ...a_k (mod n) ⇒ a^k (a_1 ...a_k ) = a_1 ...a_k (mod n) Now each a_(i ) is invertible mod n, so multiplying both sides by a_1 ^(−1) ...a_k ^(−1) , we get a^k =1(mod n) Recall that ∅(n)=k ⇒ a^(φ(n) ) =1(mod n) Hence,proved.

$$ \\ $$$$\mathrm{Assuming}\:\mathrm{FLT} \\ $$$$\left(\mathrm{a},\mathrm{n}\right)=\mathrm{1},\mathrm{n}\geqslant\mathrm{2}\Rightarrow\mathrm{a}^{\emptyset\left(\mathrm{n}\right)} \equiv\mathrm{1}\left(\mathrm{mod}\:\mathrm{n}\right) \\ $$$$\mathrm{If}\:\mathrm{n}\:\mathrm{is}\:\mathrm{prime},\mathrm{then}\:\emptyset\left(\mathrm{n}\right)\:=\:\mathrm{n}−\mathrm{1}\:\mathrm{and} \\ $$$$\mathrm{Euler}'\mathrm{s}\:\mathrm{theorem}\:\mathrm{says}\:\mathrm{a}^{\mathrm{n}−\mathrm{1}} =\mathrm{1}\left(\mathrm{mod}\:\mathrm{n}\right), \\ $$$$\mathrm{which}\:\mathrm{is}\:\mathrm{Fermat}'\mathrm{s}\:\mathrm{theorem}. \\ $$$$\mathrm{Since}\:\mathrm{n}\:\mathrm{is}\:\mathrm{prime},\:\mathrm{then}\:\mathrm{all}\:\mathrm{of}\:\mathrm{the} \\ $$$$\mathrm{numbers}\:\left\{\mathrm{1},...,\mathrm{n}−\mathrm{1}\right\}\:\mathrm{are}\:\mathrm{relatively} \\ $$$$\mathrm{prime}\:\mathrm{to}\:\mathrm{n}. \\ $$$$\Rightarrow\:\emptyset\left(\mathrm{n}\right)=\mathrm{n}−\mathrm{1} \\ $$$$ \\ $$$$\mathrm{Proof}: \\ $$$$\mathrm{Let}\:\emptyset\left(\mathrm{n}\right)=\mathrm{k},\:\mathrm{and}\:\mathrm{let}\:\left\{\mathrm{a}_{\mathrm{1}} ,\mathrm{a}_{\mathrm{2}} ,...,\mathrm{a}_{\mathrm{k}} \right\}\:\mathrm{be}\:\mathrm{a} \\ $$$$\mathrm{residue}\:\mathrm{system}\:\mathrm{mod}\:\mathrm{n}.\: \\ $$$$\mathrm{I}\:\mathrm{may}\:\mathrm{assume}\:\mathrm{that}\:\mathrm{the}\:\mathrm{a}_{\mathrm{i}} '\mathrm{s}\:\mathrm{lie}\:\mathrm{in}\:\mathrm{the} \\ $$$$\mathrm{range}\:\left\{\mathrm{1},...,\mathrm{n}−\mathrm{1}\right\}\:\mathrm{as}\:\mathrm{a}\:\mathrm{reduced} \\ $$$$\mathrm{residue}\:\mathrm{system}\:\mathrm{mod}\:\mathrm{n}\:\mathrm{is}\:\mathrm{a}\:\mathrm{set}\:\mathrm{of} \\ $$$$\mathrm{numbers}\: \\ $$$$\mathrm{a}_{\mathrm{1}} ,\mathrm{a}_{\mathrm{2}} ,\mathrm{a}_{\mathrm{3}} ,...,\mathrm{a}_{\emptyset\left(\mathrm{n}\right)} \\ $$$$\mathrm{such}\:\mathrm{that}: \\ $$$$−\mathrm{if}\:\mathrm{i}\neq\mathrm{j},\:\mathrm{then}\:\mathrm{a}_{\mathrm{i}} \neq\mathrm{a}_{\mathrm{j}} \left(\mathrm{mod}\:\mathrm{n}\right).\:\mathrm{That}\:\mathrm{is}, \\ $$$$\mathrm{the}\:\mathrm{a}'\mathrm{s}\:\mathrm{are}\:\mathrm{distinct}\:\mathrm{mod}\:\mathrm{n}. \\ $$$$−\mathrm{For}\:\mathrm{each}\:\mathrm{i},\:\left(\mathrm{a}_{\mathrm{i}} ,\mathrm{n}\right)=\mathrm{1}. \\ $$$$\mathrm{That}\:\mathrm{is},\:\mathrm{all}\:\mathrm{the}\:\mathrm{a}'\mathrm{s}\:\mathrm{are}\:\mathrm{relatively}\:\mathrm{prime} \\ $$$$\mathrm{to}\:\mathrm{n}. \\ $$$$\mathrm{Since}\:\mathrm{all}\:\mathrm{a}'\mathrm{s}\:\mathrm{are}\:\mathrm{relatively}\:\mathrm{prime}\:\mathrm{to}\:\mathrm{n}, \\ $$$$\mathrm{then}\:\mathrm{the}\:\mathrm{assumption}\:\mathrm{that}\:\mathrm{the}\:\mathrm{a}_{\mathrm{i}} '\mathrm{s}\:\mathrm{lie}\:\mathrm{in} \\ $$$$\mathrm{the}\:\mathrm{range}\:\left\{\mathrm{1},...,\mathrm{n}−\mathrm{1}\right\}\:\mathrm{is}\:\mathrm{correct}. \\ $$$$\mathrm{Since}\:\left(\mathrm{a},\mathrm{n}\right)\:=\mathrm{1},\:\left\{\mathrm{aa}_{\mathrm{1}} ,...,\mathrm{aa}_{\mathrm{k}} \right\}\:\mathrm{is}\:\mathrm{another} \\ $$$$\mathrm{reduced}\:\mathrm{residue}\:\mathrm{system}\:\mathrm{mod}\:\mathrm{n}.\:\mathrm{Since} \\ $$$$\mathrm{this}\:\mathrm{is}\:\mathrm{the}\:\mathrm{same}\:\mathrm{set}\:\mathrm{of}\:\mathrm{numbers}\:\mathrm{mod}\:\mathrm{n} \\ $$$$\mathrm{as}\:\mathrm{the}\:\mathrm{original}\:\mathrm{system},\:\mathrm{the}\:\mathrm{two} \\ $$$$\mathrm{systems}\:\mathrm{must}\:\mathrm{have}\:\mathrm{the}\:\mathrm{same}\:\mathrm{product} \\ $$$$\mathrm{mod}\:\mathrm{n}: \\ $$$$\Rightarrow\:\left(\mathrm{aa}_{\mathrm{1}} \right)\left(\mathrm{aa}_{\mathrm{2}} \right)...\left(\mathrm{aa}_{\mathrm{k}} \right)\:=\:\mathrm{a}_{\mathrm{1}} ...\mathrm{a}_{\mathrm{k}} \left(\mathrm{mod}\:\mathrm{n}\right)\: \\ $$$$\Rightarrow\:\mathrm{a}^{\mathrm{k}} \left(\mathrm{a}_{\mathrm{1}} ...\mathrm{a}_{\mathrm{k}} \right)\:=\:\mathrm{a}_{\mathrm{1}} ...\mathrm{a}_{\mathrm{k}} \left(\mathrm{mod}\:\mathrm{n}\right) \\ $$$$\mathrm{Now}\:\mathrm{each}\:\mathrm{a}_{\mathrm{i}\:} \mathrm{is}\:\mathrm{invertible}\:\mathrm{mod}\:\mathrm{n},\:\mathrm{so} \\ $$$$\mathrm{multiplying}\:\mathrm{both}\:\mathrm{sides}\:\mathrm{by} \\ $$$$\mathrm{a}_{\mathrm{1}} ^{−\mathrm{1}} ...\mathrm{a}_{\mathrm{k}} ^{−\mathrm{1}} ,\:\mathrm{we}\:\mathrm{get} \\ $$$$\mathrm{a}^{\mathrm{k}} =\mathrm{1}\left(\mathrm{mod}\:\mathrm{n}\right) \\ $$$$\mathrm{Recall}\:\mathrm{that}\:\emptyset\left(\mathrm{n}\right)=\mathrm{k} \\ $$$$\Rightarrow\:\mathrm{a}^{\phi\left(\mathrm{n}\right)\:} =\mathrm{1}\left(\mathrm{mod}\:\mathrm{n}\right) \\ $$$$\mathrm{Hence},\mathrm{proved}. \\ $$$$ \\ $$

Commented by Aina Samuel Temidayo last updated on 05/Sep/20

Is this correct?

$$\mathrm{Is}\:\mathrm{this}\:\mathrm{correct}? \\ $$$$ \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com