Question and Answers Forum

All Questions      Topic List

None Questions

Previous in All Question      Next in All Question      

Previous in None      Next in None      

Question Number 127897 by mathocean1 last updated on 02/Jan/21

show that if p (prime integer)divise a^n then p divise also a.

$$ \\ $$$$\mathrm{show}\:\mathrm{that}\:\mathrm{if}\:\:\mathrm{p}\:\:\left(\mathrm{prime}\:\mathrm{integer}\right)\mathrm{divise}\: \\ $$$$\mathrm{a}^{{n}} \:\:\mathrm{then}\:\mathrm{p}\:\mathrm{divise}\:\mathrm{also}\:\mathrm{a}.\: \\ $$

Commented by JDamian last updated on 03/Jan/21

this question seems bizarre for me because if a^n mod t = 0 ∀n>1 ⇔ a mod t = 0

$${this}\:{question}\:{seems}\:{bizarre}\:{for}\:{me}\:{because} \\ $$$$\mathrm{if}\:\:\:\mathrm{a}^{{n}} \mathrm{mod}\:{t}\:=\:\mathrm{0}\:\:\:\forall{n}>\mathrm{1}\:\:\Leftrightarrow\:\:\mathrm{a}\:\mathrm{mod}\:{t}\:\:=\:\mathrm{0} \\ $$

Answered by floor(10²Eta[1]) last updated on 03/Jan/21

(★) if n∣a and n∣b⇒n∣ax+by, x,y∈Z n∣a⇒a=nk_1 , k_1 ∈Z n∣b⇒b=nk_2 , k_2 ∈Z ax=nk_1 x and by=nk_2 y ⇒n∣ax+by=n(k_1 x+k_2 y) (■) if a≡b(mod n) and c≡d(mod n) so ac≡bd(mod n) a≡b(mod n)⇒n∣a−b c≡d(mod n)⇒n∣c−d by (★) we know that n∣c(a−b)+b(c−d)⇒n∣ac−bd ⇒ac≡bd(mod n) Now suppose p∣a^n but p∤a: ⇒a≢0(mod p) by (■) a^2 ≡b^2 (mod n) (a=c, b=d) by induction a^k ≡b^k (mod n), k∈N a≢0(mod p)⇒a^n ≢0^n =0(mod p) ⇒p∤a^n , contradiction because we suppose that p∣a^n . So if p∣a^n ⇒p∣a

$$\left(\bigstar\right)\: \\ $$$$\mathrm{if}\:\mathrm{n}\mid\mathrm{a}\:\mathrm{and}\:\mathrm{n}\mid\mathrm{b}\Rightarrow\mathrm{n}\mid\mathrm{ax}+\mathrm{by},\:\mathrm{x},\mathrm{y}\in\mathbb{Z} \\ $$$$\mathrm{n}\mid\mathrm{a}\Rightarrow\mathrm{a}=\mathrm{nk}_{\mathrm{1}} ,\:\mathrm{k}_{\mathrm{1}} \in\mathbb{Z} \\ $$$$\mathrm{n}\mid\mathrm{b}\Rightarrow\mathrm{b}=\mathrm{nk}_{\mathrm{2}} ,\:\mathrm{k}_{\mathrm{2}} \in\mathbb{Z} \\ $$$$\mathrm{ax}=\mathrm{nk}_{\mathrm{1}} \mathrm{x}\:\mathrm{and}\:\mathrm{by}=\mathrm{nk}_{\mathrm{2}} \mathrm{y} \\ $$$$\Rightarrow\mathrm{n}\mid\mathrm{ax}+\mathrm{by}=\mathrm{n}\left(\mathrm{k}_{\mathrm{1}} \mathrm{x}+\mathrm{k}_{\mathrm{2}} \mathrm{y}\right) \\ $$$$\left(\blacksquare\right) \\ $$$$\mathrm{if}\:\mathrm{a}\equiv\mathrm{b}\left(\mathrm{mod}\:\mathrm{n}\right)\:\mathrm{and}\:\mathrm{c}\equiv\mathrm{d}\left(\mathrm{mod}\:\mathrm{n}\right)\:\mathrm{so}\: \\ $$$$\mathrm{ac}\equiv\mathrm{bd}\left(\mathrm{mod}\:\mathrm{n}\right) \\ $$$$\mathrm{a}\equiv\mathrm{b}\left(\mathrm{mod}\:\mathrm{n}\right)\Rightarrow\mathrm{n}\mid\mathrm{a}−\mathrm{b} \\ $$$$\mathrm{c}\equiv\mathrm{d}\left(\mathrm{mod}\:\mathrm{n}\right)\Rightarrow\mathrm{n}\mid\mathrm{c}−\mathrm{d} \\ $$$$\mathrm{by}\:\left(\bigstar\right)\:\mathrm{we}\:\mathrm{know}\:\mathrm{that} \\ $$$$\mathrm{n}\mid\mathrm{c}\left(\mathrm{a}−\mathrm{b}\right)+\mathrm{b}\left(\mathrm{c}−\mathrm{d}\right)\Rightarrow\mathrm{n}\mid\mathrm{ac}−\mathrm{bd} \\ $$$$\Rightarrow\mathrm{ac}\equiv\mathrm{bd}\left(\mathrm{mod}\:\mathrm{n}\right) \\ $$$$ \\ $$$$ \\ $$$$\mathrm{Now}\:\mathrm{suppose}\:\mathrm{p}\mid\mathrm{a}^{\mathrm{n}} \:\mathrm{but}\:\mathrm{p}\nmid\mathrm{a}: \\ $$$$\Rightarrow\mathrm{a}≢\mathrm{0}\left(\mathrm{mod}\:\mathrm{p}\right) \\ $$$$\mathrm{by}\:\left(\blacksquare\right)\:\mathrm{a}^{\mathrm{2}} \equiv\mathrm{b}^{\mathrm{2}} \left(\mathrm{mod}\:\mathrm{n}\right)\:\left(\mathrm{a}=\mathrm{c},\:\mathrm{b}=\mathrm{d}\right) \\ $$$$\mathrm{by}\:\mathrm{induction}\:\mathrm{a}^{\mathrm{k}} \equiv\mathrm{b}^{\mathrm{k}} \left(\mathrm{mod}\:\mathrm{n}\right),\:\mathrm{k}\in\mathbb{N} \\ $$$$\mathrm{a}≢\mathrm{0}\left(\mathrm{mod}\:\mathrm{p}\right)\Rightarrow\mathrm{a}^{\mathrm{n}} ≢\mathrm{0}^{\mathrm{n}} =\mathrm{0}\left(\mathrm{mod}\:\mathrm{p}\right) \\ $$$$\Rightarrow\mathrm{p}\nmid\mathrm{a}^{\mathrm{n}} ,\:\mathrm{contradiction}\:\mathrm{because}\:\mathrm{we}\:\mathrm{suppose} \\ $$$$\mathrm{that}\:\mathrm{p}\mid\mathrm{a}^{\mathrm{n}} .\:\mathrm{So}\:\mathrm{if}\:\mathrm{p}\mid\mathrm{a}^{\mathrm{n}} \Rightarrow\mathrm{p}\mid\mathrm{a} \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com