Menu Close

show-that-if-p-prime-integer-divise-a-n-then-p-divise-also-a-

Tinku Tara 0 Comments
Pin




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

Pin

Leave a Reply

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