[PDF] a4 integers 17 (2017) a short note on reduced residues - EMIS

950_6r4.pdf #A4INTEGERS17(2017)

ASHORTNOTEONREDUCEDRESIDUES

PascalStumpf

DepartmentofMathematics,UniversityofW¨urzburg,Germany littlefriend@mathlino.org Received:11/25/14,Revised:5/31/16,Accepted:1/26/17,Published:2/13/17

Abstract

WeansweraquestionduetoBernardoRecam´anaboutthelowerboundbehavior ofthemaximumpossiblelengthamongarithmeticprogressionsintheleastreduced residuesystemmodulon,asn!1.Wealsoprovideanupperbound.

1.Introduction

Foranypositiveintegern>1,let

A(n)={a2Z:0 bethe(nonempty)setofallsmallerpositiveintegersrelativelyprimeton,orin otherwordstheleastreducedresiduesystemmodulon,andletusdefinef(n)as themaximumpossiblelengthamongallarithmeticprogressionsinA(n). Inaletterfrom1995(seeChapterB40of[1])BernardoRecam´anaskediff(n) tendstoinfinitywithn,i.e.,ifforeachk2Z + thereexistsaconstantn k suchthat A(n)containsanarithmeticprogressionoflengthkforalln>n k . OneverynicebutdeepresultcomingtomindhereisthatofGreenandTao[2] tellingusaboutarbitrarilylongarithmeticprogressionsintheprimes,andinfactit isapromisingindicatorforapositiveanswertoourquestion,sinceA(n)contains allprimeslessthannexceptitsprimefactors.However,itturnsoutthatwecan provethetruthofourconjecturebyusingonlyelementarymethods,andinwhat followswepresentonesuchsolution.

2.IdeasandProof

Beforewestartcollectingsomelowerboundsforf(n),letusquicklyconsiderafew examplesofA(n)andf(n)asillustratedinthefollowingfigures:

INTEGERS:17(2017)2

Lemma1.Forn>1,wehavef(n)>max{(p1)/2,n/P},wherepisthelargest primefactorofnandPisthesquarefreeproductofallprimefactorsofn. Proof.Accordingtotheprimefactorizationofn,webuildupourproofbyworking throughallofthefollowingpossiblecases. First,letussupposenisprimeitself;thenexactlyallsmallerpositiveintegers from1upton1arerelativelyprimetonandformanarithmeticprogressionof lengthn1withcommondi↵erence1,whichmeansf(n)=n1.

Inthemoregeneralcasen=p

r ,wherepisprimeandr2Z + ,wesimilarlystill have{1,...,p1}⇢A(n)andsof(n)>p1.Butifr>2wecanalsolook atthenumbers1+m·pfor06m

p r1 =n/phere.

Next,letusconsidersquarefreenumbersn=p

1 p 2 ...p d ,whered>2and26 p 1

1)·q=1+nq61+n2 isalreadynotdivisiblebyanyoftheprimesp 1 ,p 2 ,...,p d1 ,althoughwearenot sureaboutnon-divisibilitybyp d yet.However,togethera 0 ,a 1 ,...,a p d 1 represent

INTEGERS:17(2017)3

acompleteresiduesystemmodulop d ,becauseifa x ⌘a y (modp d )forsome06 x1)/2withcommondi↵erenceq

completelycontainedinsideA(n),whichdeliversf(n)>(p d 1)/2.

Finally,letusintroduceexponentsr

1 ,r 2 ,...,r d 2Z + suchthatwecancoverall remainingnumbersn=p r1 1 p r2 2 ...p r d d ,wherer 1 +r 2 +...+r d >d.Becausenhas thesameprimefactorsasp 1 p 2 ...p d ,wefindA(p 1 p 2 ...p d )buildsasubsetof {a+m·p 1 p 2 ...p d :a2A(p 1 p 2 ...p d ),06m

Infact,wehavegcd(a,n)=1ifandonlyifgcd(a,p 1 p 2 ...p d )=1,forallintegersa, andhencef(n)>f(p 1 p 2 ...p d )>(p d

1)/2.Ontheotherhand,wemightagain

doabitbetterbylookingatthenumbers1+m·p 1 p 2 ...p d forminganarithmetic progressionoflengthp r11 1 p r21 2 ...p r d 1 d withcommondi↵erencep 1 p 2 ...p d ,and combiningbothideasleadsustof(n)>max{(p d

1)/2,n/(p

1 p 2 ...p d )}.

Theorem1.Foreachk2Z

+ ,thereexistsaconstantn k suchthatA(n)contains anarithmeticprogressionoflengthkforalln>n k .

Proof.LetP

2k betheproductofallprimesnotexceeding2kandputn k =k·P 2k >1·2.Moreover,letusfixsomen>n k ,and(asinLemma1)denoteitslargest primefactorbyp.Ifp>2k+1,weimmediatelyarriveat (p1)/2>((2k+1)1)/2=k. Intheothercasep<2k+1,wenotethatallprimefactorsofndonotexceed2k, implyingtheirproductPdividesP 2k ,andsoinparticular n/P>n k /P=k·P 2k /P>k·1. Combiningeverythingwereachf(n)>max{(p1)/2,n/P}>k,andourclaim follows. Sofarwemainlyworkedonlowerboundsforf(n).Asalaststep,letuschange ourpointofviewandconcludebyshowing:

Theorem2.Forn>1,wealsohavef(n)6max{(p1)/1,n/P}.

INTEGERS:17(2017)4

Proof.Supposea

1 ,a 2 ,...,a s isanarithmeticprogressionoflengthswithcommon di ↵ erenceqcontainedinA(n).Nowletusfocusabitmoreonq. Ifq>P,wecanonlycomeuptos6n/P,sinceotherwises>n/Pimplies a s =a 1 +(s1)·q>1+((n/P+1)1)·P=n+1, andourlastmemberwouldnotbeinA(n)anymore.Intheothercaseqp 0 ,thefirstp 0 membersa 1 ,a 2 ,...,a p

0dorepresentacomplete

residuesystemmodulop 0 .Thereforeoneofthem,beingamultipleofp 0 ,couldnot lieinA(n)anymore,leavingusonlys6p 0

16p1lefthere.Unitingbothcases

wereachf(n)6max{n/P,p1},asdesired.

3.FutureWork

Afterhavingestablishedlowerandupperboundsforf(n),especiallyinthecase ofsquarefreenumbersn,aninterestingquestionseemstobewhether,onaverage, f(n)iscloserto(p1)/2orp1.Ourexamplesindicatethatitcanbevery neartoboththresholds.Anothertaskistoimproveonthegivenbordern k inour maintheorem.Forbothaimsonecouldhopetogetbetterestimatesbyusingmore advancedmethods. Acknowledgements.IwouldliketothankMiriamandherbrotherChristian Goldschmiedforalwaysencouragingmetowritethingsdownandmakingmyfirst paperpossible,andtheanonymousrefereeforveryusefulcomments.

References

[1]R.Guy,UnsolvedProblemsinNumberTheory,Springer,2004. [2]B.GreenandT.Tao,Theprimescontainarbitrarilylongarithmeticprogressions,Annalsof

Mathematics(2)167(2008),481-547.

Politique de confidentialité -Privacy policy