matematikk.net

La [tex]a>1[/tex], [tex]n>0[/tex] være to heltall slik at [tex]a^n+1[/tex] er et primtall. Vis at [tex]d(a^n-1) \geq n[/tex].

Føler at jeg ikke helt har kommet i mål, men det jeg fant ut var at dersom a^n+1 skal være et primtall, må n være på formen n=2^k, altså ikke delelig med noe oddetall, ellers ville vi kunnet faktorisere a^n+1 "algebraisk".

Vi har altså at [tex]a^n-1=a^{2^k}-1[/tex] dermed kan faktoriseres algebraisk:

[tex]a^{2^k}-1=(a-1)(a+1)(a^2+1)(a^4+1)(a^8+1)...(a^{2^{k-1}}) [/tex].

For at [tex]d(a^{2^k}-1)[/tex] skal være større enn eller lik n er det vel nok at det er k distinkte primfaktorer, men det er jeg ikke helt sikker på hvordan jeg kan vise ut fra likheten over.

Jeg bruker det plutarco har kommet fram til. Hvis [tex]n =2^rk[/tex] der k > 1 er odde er [tex]a^{2^rk}+1=(a+1)(a^{2^r}-a^{2^r-1}+...+1)[/tex] og dermed ikke et primtall. Dermed er [tex]n=2^r[/tex]. Videre er [tex]a^{2^r}-1=(a-1)(a+1)(a^2+1)...(a^{2^{r-1}}+1)[/tex]. Vi merker oss at a må være et partall, hvis ikke vil 2 dele uttrykket.

Vi ser på de r faktorene [tex]a+1,a^2+1,...,a^{r-1}+1[/tex] og viser at de ikke har noen felles primfaktorer:

La p være et primtall og anta at p deler [tex]a^t+1[/tex] og [tex]a^s+1[/tex] der t>s. Da vil p dele
[tex]a^t+1-a^{t-s}(a^s+1)=1-a^{t-s}[/tex], så t deler [tex]a^{t-s}-1[/tex]. Dersom [tex]t-s=s[/tex], så vil p dele [tex]a^{s}+1-(a^{t-s}-1)=a[/tex] som er umulig, siden dette medfører at p|1.
Dersom t-s>s, har vi at p deler [tex]a^{t-2s}(a^s+1)-(a^{t-s}-1)=a^{t-2s}+1[/tex], og hvis t-s<s, har vi at p deler [tex]a^s+1-a^{2s-t}(a^{t-s}-1)=a^{2s-t}+1[/tex].

Summen av eksponentene i de to nye uttrykkene når t-s>s og t-s<s er henholdsvis t-2s+s=t-s<t+s og 2s-t+s<2s<t+s. Eksponentene må i begge tilfeller være større enn 0. Fortsetter vi å redusere eksponentene slik ser vi at til slutt ender vi opp med at eksponentene er like, noe som er umulig.

Det betyr at vi har minst r forskjellige primfaktorer, og som plutarco påpekte medfører dette at vi har minst 2^r=n forskjellige divisorer.

Det er riktig dette.