Question Number 13529 by Tinkutara last updated on 20/May/17
$$\mathrm{Let}\:{p}\:\mathrm{be}\:\mathrm{a}\:\mathrm{prime}\:\mathrm{number}\:>\:\mathrm{3}.\:\mathrm{What} \\ $$$$\mathrm{is}\:\mathrm{the}\:\mathrm{remainder}\:\mathrm{when}\:{p}^{\mathrm{2}} \:\mathrm{is}\:\mathrm{divided}\:\mathrm{by} \\ $$$$\mathrm{12}? \\ $$
Commented by prakash jain last updated on 20/May/17
$$\mathrm{Any}\:\mathrm{prime}\:\mathrm{number}\:\mathrm{greater}\:\mathrm{than} \\ $$$$\mathrm{3}\:\mathrm{is}\:\mathrm{of}\:\mathrm{the}\:\mathrm{form} \\ $$$$\mathrm{6}{n}+\mathrm{1} \\ $$$$\mathrm{6}{n}−\mathrm{1}\:\left(\mathrm{or}\:\mathrm{6n}+\mathrm{5}\right) \\ $$$$\mathrm{since}\:\mathrm{6}{n}+\mathrm{2},\mathrm{6}{n}+\mathrm{3},\mathrm{6}{n}+\mathrm{4}\:\mathrm{are}\:\mathrm{composites}. \\ $$$$\left(\mathrm{6n}+\mathrm{1}\right)^{\mathrm{2}} =\mathrm{36n}^{\mathrm{2}} +\mathrm{12n}+\mathrm{1} \\ $$$$\left(\mathrm{6n}+\mathrm{1}\right)^{\mathrm{2}} \:\mathrm{mod}\:\mathrm{12}=\mathrm{1} \\ $$$$\left(\mathrm{6n}−\mathrm{1}\right)^{\mathrm{2}} =\mathrm{36n}^{\mathrm{2}} −\mathrm{12n}+\mathrm{1} \\ $$$$\left(\mathrm{6n}−\mathrm{1}\right)^{\mathrm{2}} \:\mathrm{mod}\:\mathrm{12}\:=\mathrm{1} \\ $$$$\mathrm{so}\:\mathrm{for}\:\mathrm{all}\:\mathrm{primes}\:{p}\:\mathrm{greater}>\mathrm{3} \\ $$$${p}^{\mathrm{2}} \:\mathrm{mod}\:\mathrm{12}=\mathrm{1} \\ $$
Commented by RasheedSindhi last updated on 20/May/17
$$\boldsymbol{{e}}^{\boldsymbol{{x}}} {cellent}! \\ $$
Commented by mrW1 last updated on 20/May/17
$${Can}\:{you}\:{please}\:{explain}\:{why}\:{any}\:{prime} \\ $$$${is}\:{of}\:{the}\:{form}\:\mathrm{6}{n}\pm\mathrm{1}? \\ $$
Commented by prakash jain last updated on 20/May/17
$${all}\:{integer}\:{can}\:{be}\:{written}\:{as} \\ $$$$\mathrm{6}{n}+{m}\:{when}\:{m}\in\left\{\mathrm{1},\mathrm{2},\mathrm{3},\mathrm{4},\mathrm{5}\right\} \\ $$$$\mathrm{6}{n}+\mathrm{2}\:=\mathrm{2}\left(\mathrm{3}{n}+\mathrm{1}\right)\:{not}\:{a}\:{prime} \\ $$$$\mathrm{6}{n}+\mathrm{3}\:=\mathrm{3}\left(\mathrm{2}{n}+\mathrm{1}\right)\:{not}\:{a}\:{prime} \\ $$$$\mathrm{6}{n}+\mathrm{4}\:=\mathrm{2}\left(\mathrm{3}{n}+\mathrm{2}\right)\:{not}\:{a}\:{prime} \\ $$$$\mathrm{so}\:\mathrm{only}\:\mathrm{two}\:\mathrm{possibilities}\:\mathrm{of} \\ $$$$\mathrm{a}\:\mathrm{prime}\:\mathrm{number}>\mathrm{5},\:\mathrm{6}{n}+\mathrm{1},\:\mathrm{6}{n}+\mathrm{5} \\ $$$${we}\:{write}\:\mathrm{6}{n}+\mathrm{5}\:{as}\:\mathrm{6}{n}−\mathrm{1}\:\mathrm{so}\:\mathrm{that} \\ $$$$\mathrm{we}\:\mathrm{cover}\:\mathrm{number}\:\mathrm{5}\:\mathrm{as}\:\mathrm{well}. \\ $$$$\mathrm{6}{n}+\mathrm{5}=\mathrm{6}\left({n}+\mathrm{1}\right)−\mathrm{1} \\ $$$$\mathrm{6}{n}+\mathrm{1}=\mathrm{6}{n}−\mathrm{1} \\ $$$$\mathrm{so}\:\mathrm{all}\:\mathrm{primes}\:>\mathrm{3}\:\mathrm{are}\:\mathrm{of}\:\mathrm{the}\:\mathrm{form} \\ $$$$\mathrm{6}{n}\pm\mathrm{1} \\ $$
Commented by mrW1 last updated on 20/May/17
$${Thanks}\:{very}\:{much}! \\ $$
Commented by Tinkutara last updated on 21/May/17
$$\mathrm{It}\:\mathrm{is}\:\mathrm{also}\:\mathrm{called}\:\mathrm{Euclid}'\mathrm{s}\:\mathrm{Division}\:\mathrm{Lemma} \\ $$$$\mathrm{where}\:{a}\:=\:{bq}\:+\:{r},\:\mathrm{0}\:\leqslant\:{r}\:<\:{b}. \\ $$
Commented by mrW1 last updated on 22/May/17
$${According}\:{to}\:{the}\:{method}\:{of}\:\boldsymbol{{Prakash}} \\ $$$${we}\:{can}\:{prove}\: \\ $$$${p}^{\mathrm{2}} \:\left({mod}\:\mathrm{4}\right)\:=\mathrm{1} \\ $$$${p}^{\mathrm{2}} \:\left({mod}\:\mathrm{8}\right)\:=\mathrm{1} \\ $$$${p}^{\mathrm{2}} \:\left({mod}\:\mathrm{12}\right)\:=\mathrm{1} \\ $$$$ \\ $$$${The}\:{question}\:{is}\:{now}\:{if}\:{there}\:{exists}\:{a}\: \\ $$$${further}\:{positive}\:{integer}\:{n}>\mathrm{12}\:{so}\:{that} \\ $$$${p}^{\mathrm{2}} \:\left({mod}\:{n}\right)=\mathrm{1}\:{for}\:{every}\:{prime}\:{number}\:{p} \\ $$$${upon}\:{a}\:{certain}\:{one}? \\ $$