Menu Close

Assuming-FLT-prove-Fermat-Euler-theorem-a-n-1-n-2-a-n-1-mod-n-

Tinku Tara 0 Comments
Pin




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}? \\ $$$$ \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *