Let-p-be-a-prime-number-gt-3-What-is-the-remainder-when-p-2-is-divided-by-12-

Question Number 13529 by Tinkutara last updated on 20/May/17

Let p be a prime number > 3. What is the remainder when p^2 is divided by 12?

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

Any prime number greater than 3 is of the form 6n+1 6n−1 (or 6n+5) since 6n+2,6n+3,6n+4 are composites. (6n+1)^2 =36n^2 +12n+1 (6n+1)^2 mod 12=1 (6n−1)^2 =36n^2 −12n+1 (6n−1)^2 mod 12 =1 so for all primes p greater>3 p^2 mod 12=1

$$\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 6n±1?

$${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 6n+m when m∈{1,2,3,4,5} 6n+2 =2(3n+1) not a prime 6n+3 =3(2n+1) not a prime 6n+4 =2(3n+2) not a prime so only two possibilities of a prime number>5, 6n+1, 6n+5 we write 6n+5 as 6n−1 so that we cover number 5 as well. 6n+5=6(n+1)−1 6n+1=6n−1 so all primes >3 are of the form 6n±1

$${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

It is also called Euclid′s Division Lemma where a = bq + r, 0 ≤ r < b.

$$\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 Prakash we can prove p^2 (mod 4) =1 p^2 (mod 8) =1 p^2 (mod 12) =1 The question is now if there exists a further positive integer n>12 so that p^2 (mod n)=1 for every prime number p upon a certain one?

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

Facebook Tweet Pin

Let-p-be-a-prime-number-gt-3-What-is-the-remainder-when-p-2-is-divided-by-12-

Leave a Reply Cancel reply