Question and Answers Forum

All Questions      Topic List

Number Theory Questions

Previous in All Question      Next in All Question      

Previous in Number Theory      Next in Number Theory      

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 byprakash 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 byRasheedSindhi last updated on 20/May/17

e^x cellent!

$$\boldsymbol{{e}}^{\boldsymbol{{x}}} {cellent}! \\ $$

Commented bymrW1 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 byprakash 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 bymrW1 last updated on 20/May/17

Thanks very much!

$${Thanks}\:{very}\:{much}! \\ $$

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

Terms of Service

Privacy Policy

Contact: info@tinkutara.com