square, cube & etc

PerfectSquares,Cubes,FourthPowersandMore

Manyproblemsinnumbertheoryinvolveexpressionswithperfectsquares,perfectcubes

orperfectfourthpowers.Thereareproblemsthatrequireustofindintegersolutionsto

equationswithunknownexponents.BelowIwilllistveralcommontypesofproblems

andstrategiestotacklethem.Ofcour,thelistisnotexhaustive.

1.Findingintegersolutionstoanequationinvolvingperfectsquares,cubesor

fourthpowers.Manyoftheproblemscanbetackledbyconsideringthepos-

sibleresidues,moduloasuitablenumber.Forperfectsquares,tryingconsidering

modulo4,8,16,3,5,7,11or13.Forperfectcubes,itmaybeufultotake

modulo7,9or,ocassionally,modulo13.Forperfectfourthpowers,youmight

wishtoconsidermodulo5or16.Ofcour,thearejustsuggestions,andit

reallydependsontheproblem.

Forequationsthatinvolveonlyperfectsquaresintwovariables,itmaybeufulto

considertheequationasaquadraticinonevariable,anduthefactthatdiscrim-

inantisnon-negativeforasolutiontoexist,orthatthediscriminantisaperfect

square(inorderforthesolutionstobeaninteger).Thisapproach,however,has

limitedusandmaysometimesleadtoadeadend.

Anotherapproachwouldbetotrytofactorithegivenexpressiontotrytoderive

ufuldivisibilitypropertiesorinequalitiesthatwillallowyoutoreducethescope

ofconsiderationtojustafewcas.Factorisationisalwaysoneapproachthatyou

shouldkeepinmind,asitmaysometimesyieldsurprisingresults.

Alternatively,toshowthatacertainequationhasnointegersolutions,wecanalso

uFermat’smethodofinfinitedescent.Toshowthatanequationinvolvingper-

fectsquareshasinfinitelymanysolutions,wemaywanttoshowthattheequation

canbereducedtofindingthesolutionstopythagoreantriples,forwhichtherewill

beinfinitelymanysolutions.Thetechniqueswillnotbecoveredindetailinthis

lesson.

2.Provethatacertainexpressionisalwaysaperfectsquare(orperfectcube).

Themoststraightforwardwaytodothisistoshowthatitcanalwaysbefactorid

intoaperfectsquare(orcube)!Thefollowingresultmaybeuful:Ifabis

aperfectsquareandgcd(a,b)=1,thenaandbmustalsobeperfectsquares.

Anotherstandardapproachistoprovebycontradiction.Suppotheexpression

isnotaperfectsquare,andshowthatitleadstoacontradiction.

Ifthequestionisofthetype“provethat(someexpression)isalwaysaperfect

squareforallvaluesofn”,thenyoumaywanttoconsiderusingmathematical

induction.

3.Provethatacertainexpressionisneveraperfectsquare.Simpleproblems

ofthissortcanbedonebyconsideringtheresidueoftheexpressionmoduloa

suitablenumber,sayn.Ifitisnotaquadraticresidueofn,thenitcannotbea

perfectsquare.

Anothercommontechniqueinvolvesboundingbetweenconcutivesquares(or

concutivecubes).Ifn<x<(n+1)foranintegern,thenxcannotbeaperfect

22

square.

Alternatively,ifweareabletoshowthataprimeporanoddpoweroftheprime,

p,dividestheexpressionexactly,thentheexpressioncannotbeaperfect

2k+1

square.

PreparedbyHoJunWei

HwaChongMathOlympiadProgramme(Open)

1

4.Aprobleminvolvingtwogivenexpressionsthatarebothperfectsquares.If

youaregivenexpressionAandexpressionBandyouaretoldthattheyareboth

perfectsquares,thenyoumightwishtoask,whatconditionsmustholdforboth

ofthemtobeperfectsquares?IfweletA=mandB=n,itmaybeufulto

22

considerA−B=(m+n)(m−n).Itmayalsohelptoconsiderifmornmustbe

oddoreven(bytakingAandBmodulo4,forinstance).Consideringresidues

oftheexpressionsmoduloasuitablenumbermaysometimesalsoleadyoutoa

solution(oracontradiction).

Iftheproblemwantsyouto“findallintegersxsuchthatAandBarebothperfect

squares”,whereAandBareexpressionsinvolvingx,youmightwanttofinda

boundforx.Forinstance,againwesuppoA=mandB=n.Thenyoumay

22

wanttoshowthatifxexceedsacertainnumber,thenm<n<(m+1),thusA

222

andBcannotbothbeperfectsquares,acontradiction.

AnotherapproachtothiskindofproblemistotrytoobtainaPell’sequationfrom

thegivenexpressions.However,thatisbeyondthescopeofourlesson.

5.EquationswithunknownexponentsIftheequationhastermswithanunknown

exponente.g.7,thenwemaywishtoconsiderresiduesmoduloasuitablenumber

x

to‘eliminate’theterm.Forinstance,wecanumod7togetridof7.Alterna-

x

tively,mod3andmod8arealsoufulsince7≡1(mod3)and7≡±1(mod

xx

8).Thismightleadustosomethinguful.Alternatively,iftherearetwoormore

termswithunknownexponents,suchas3+4=5,thenconsideringmod3and

xyz

mod4respectively,youwillobtainxandzareeven.Theequationcanthenbe

factoridasadifferenceofsquares.

ResiduesofSquares,CubesandFourthPowers

Thefollowingresultsforperfectsquaresareeasytoverify:

•x≡0,1(mod4).

2

Moreprecily,x≡0(mod4)⇔xiseven,andx≡1(mod4)⇔xisodd.

22

•x≡0,1,4(mod8).

2

Inparticular,notethatx≡1(mod8)⇔xisodd.

2

•x≡0,1,4,9(mod16)

2

•x≡0,1(mod3)

2

•x≡0,1,4(mod5)

2

•x≡0,1,2,4(mod7)

2

Herearesomeufulpropertiesofperfectcubes:

•x≡0,±1(mod7)

3

•x≡0,±1(mod9)

3

Finally,forperfectfourthpowers:

•x≡0,1(mod5)

4

•x≡0,1(mod16)

4

PreparedbyHoJunWei

HwaChongMathOlympiadProgramme(Open)

2

Example1.Findallpairsofprimenumbers(p,q)suchthat

(RussiaMO)

p−q=(p+q).

352

Example2.Letdbeanypositiveintegerthatisnot2,5or13.Provethatatleastoneof

thenumbers2d−1,5d−1,13d−1isnotaperfectsquare.

Example3.Findallnon-negativeintegersolutionstotheequation3−y=1.

x3

Example4.Provethattherearenointegersxandysuchthat

(Putnam1954)

x+3xy−2y=122.

22

PreparedbyHoJunWei

HwaChongMathOlympiadProgramme(Open)

3

ClassroomProblems

1.Letnbeanaturalnumbersuchthat2n+1and3n+1arebothperfectsquares.

Provethat5n+3iscomposite.

2.If2n+1and3n+1arebothperfectsquares,provethatnmustbedivisibleby40.

3.Determineallprimespsuchthat5+12isaperfectsquare.

pp

√

4.Letnbeaninteger.Provethatif228n+1+2isaninteger,thenitisaperfect

2

square.

5.Findallnaturalnumbersnsuchthat2+2+2isaperfectsquare.

811n

6.Provethatthesystemofequations

x+6y=z

222

6x+y=t

222

hasnonon-trivialsolutions.

7.Findallintegersxandysuchthatx+3yandy+3xarebothperfectsquares.

22

8.Findallintegersxandysuchthatx+y,x+2yand2x+yareallperfectsquares.

4442009

+x+...+x=2009.9.Determineallintegersolutionstotheequationx

128

10.Findallnon-negativeintegers(x,y)satisfying(xy−7)=x+y.

222

11.Provethattheequationy=x−4hasnointegersolutions.

25

12.Findallpairsofintegers(x,y)satisfyingtheequation

(SMO(S)2004/Round2)

(x+y)=1+16y.

222

13.Showthattheequation2−1=zhasnointegersolutionsifx,m>1.

xm

14.Dothereexistintegersxandysuchthat19=x+y?Justify

(SMO(O)1998/B3)

1934

youranswer.

15.Findallpairsofnonnegativeintegers(x,y)satisfying

(NTST2007)

(14y)+y=2007.

xx+y

16.Whatisthesmallestpositiveintegernsuchthatthereexists

(IMOshortlist2002)

3332002

+x+...+x=2002?integersx,x,...,xsatisfyingx

12n

12

n

17.Determineallpairs(x,y)ofintegerssuchthat

(IMO2006)

1+2+2=y.

x2x+12

PreparedbyHoJunWei

HwaChongMathOlympiadProgramme(Open)

4