La n > 6 være et heltall og la [tex]a_1,a_2,...,a_k[/tex] være de positive heltallene mindre enn n som er relativt primske med n. Hvis
[tex]a_2-a_1=a_3-a_2=...=a_k-a_{k-1}[/tex] > 0, vis at n enten er et primtall eller en potens av 2.
Heltallsoppgave
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Først av alt ser vi at siden [tex]a_i-a_{i-1}=d>0[/tex] må følgen [tex]a_i[/tex] være monotont stigende, og altså bestå av de positive heltallene relativt primiske til n 'i riktig rekkefølge'. Om [tex]d=1[/tex] er alle heltall mindre enn [tex]n[/tex] innbyrdes primiske med [tex]n[/tex], og [tex]n[/tex] er altså et primtall. Om [tex]d=2[/tex] er alle oddetall mindre enn [tex]n[/tex] (da [tex]a_1=1[/tex]) innbyrdes primiske med [tex]n[/tex], og [tex]n[/tex] er en toerpotens.
Anta så at [tex]d \geq 3[/tex]. Vi viser så at [tex]d[/tex] ikke deler [tex]n[/tex]. Anta at [tex]=dm[/tex]. Siden [tex]a_k=n-1[/tex] har vi da [tex]d(k-1)+1=n-1[/tex], så [tex]d(k-1)=dm-2[/tex], og [tex]d|2[/tex], som er umulig, da [tex]d>2[/tex]. Altså finnes et primtall [tex]q[/tex] slik at [tex]q|n[/tex], men [tex]q \not | d[/tex].
Betrakt så kongruensen [tex]md \equiv -1 \pmod q[/tex]. Da [tex]q \not | d[/tex] har denne en løsning [tex]m < q[/tex]. Anta foreløpig at [tex]q<k[/tex] for å ikke gjøre beviset uleselig. Vi har da at [tex]a_{m+1}=md+1 \equiv 0 \pmod q[/tex] av konstruksjon, så [tex]q | a_m[/tex]. Vi har av definisjonen at [tex]\gcd(a_{m+1}, n)=1[/tex], men [tex]q[/tex] deler både [tex]a_{m+1}[/tex] og [tex]n[/tex], så dette er en motsigelse, og vi er ferdige.
Det vil si - vi er ferdige om vi viser at [tex]a_{m+1}[/tex] faktisk er en av [tex]a_1 , \ldots a_k[/tex], dvs [tex]m+1\leq k[/tex]. Dette følger om vi kan vise [tex]q \leq k[/tex]. Da [tex]k=\phi(n)[/tex] og [tex]\phi(n)=\prod(p_i-1)p_i ^{a_i -1}[/tex] der [tex]n=\prod p_i ^a_i[/tex] (og at [tex]p_j=q[/tex]) har vi at [tex]k=\phi(n)=\phi(q^a_j)\phi(\frac n {q^a_j}) \geq \phi(q^a_j) = (q-1)q^{a_j-1} \geq q-1[/tex] der vi har likhet i den første ulikheten kun hvis [tex]n=q^{a_j}[/tex] (eller [tex]n=2 q^{a_j}[/tex]), og i den andre kun hvis [tex]a_j=1[/tex]. Om ikke begge disse er tilfellet har vi [tex]k>q-1[/tex], så [tex]k \geq q \geq m+1[/tex] som ønsket.
Det gjenstår altså kun tilfellet [tex]n=2q[/tex] for et primtall [tex]q[/tex]. Om [tex]q \not = 3[/tex] har vi [tex]d=2[/tex], siden [tex]a_1=1[/tex] og [tex]\gcd(2q, 3) =1[/tex] gir [tex]a_2=3[/tex]. Men da er alle oddetall mindre enn [tex]n[/tex] innbyrdes primiske til [tex]n[/tex], som er umulig da [tex]q[/tex] er et oddetall mindre enn [tex]n[/tex]. Om [tex]q=3[/tex] har vi [tex]n=6[/tex], som motsier kravet [tex]n>6[/tex]. Altså har vi vist at [tex]k \geq m+1[/tex], og med dette fullført beviset vårt, og vi er faktisk ferdige.
Anta så at [tex]d \geq 3[/tex]. Vi viser så at [tex]d[/tex] ikke deler [tex]n[/tex]. Anta at [tex]=dm[/tex]. Siden [tex]a_k=n-1[/tex] har vi da [tex]d(k-1)+1=n-1[/tex], så [tex]d(k-1)=dm-2[/tex], og [tex]d|2[/tex], som er umulig, da [tex]d>2[/tex]. Altså finnes et primtall [tex]q[/tex] slik at [tex]q|n[/tex], men [tex]q \not | d[/tex].
Betrakt så kongruensen [tex]md \equiv -1 \pmod q[/tex]. Da [tex]q \not | d[/tex] har denne en løsning [tex]m < q[/tex]. Anta foreløpig at [tex]q<k[/tex] for å ikke gjøre beviset uleselig. Vi har da at [tex]a_{m+1}=md+1 \equiv 0 \pmod q[/tex] av konstruksjon, så [tex]q | a_m[/tex]. Vi har av definisjonen at [tex]\gcd(a_{m+1}, n)=1[/tex], men [tex]q[/tex] deler både [tex]a_{m+1}[/tex] og [tex]n[/tex], så dette er en motsigelse, og vi er ferdige.
Det vil si - vi er ferdige om vi viser at [tex]a_{m+1}[/tex] faktisk er en av [tex]a_1 , \ldots a_k[/tex], dvs [tex]m+1\leq k[/tex]. Dette følger om vi kan vise [tex]q \leq k[/tex]. Da [tex]k=\phi(n)[/tex] og [tex]\phi(n)=\prod(p_i-1)p_i ^{a_i -1}[/tex] der [tex]n=\prod p_i ^a_i[/tex] (og at [tex]p_j=q[/tex]) har vi at [tex]k=\phi(n)=\phi(q^a_j)\phi(\frac n {q^a_j}) \geq \phi(q^a_j) = (q-1)q^{a_j-1} \geq q-1[/tex] der vi har likhet i den første ulikheten kun hvis [tex]n=q^{a_j}[/tex] (eller [tex]n=2 q^{a_j}[/tex]), og i den andre kun hvis [tex]a_j=1[/tex]. Om ikke begge disse er tilfellet har vi [tex]k>q-1[/tex], så [tex]k \geq q \geq m+1[/tex] som ønsket.
Det gjenstår altså kun tilfellet [tex]n=2q[/tex] for et primtall [tex]q[/tex]. Om [tex]q \not = 3[/tex] har vi [tex]d=2[/tex], siden [tex]a_1=1[/tex] og [tex]\gcd(2q, 3) =1[/tex] gir [tex]a_2=3[/tex]. Men da er alle oddetall mindre enn [tex]n[/tex] innbyrdes primiske til [tex]n[/tex], som er umulig da [tex]q[/tex] er et oddetall mindre enn [tex]n[/tex]. Om [tex]q=3[/tex] har vi [tex]n=6[/tex], som motsier kravet [tex]n>6[/tex]. Altså har vi vist at [tex]k \geq m+1[/tex], og med dette fullført beviset vårt, og vi er faktisk ferdige.
-
Solar Plexsus
- Over-Guru
- Posts: 1686
- Joined: 03/10-2005 12:09
Det går an å vise at [tex]d \:>\: 2[/tex] gir en selvmotsigelse på følgende alternative måte:
[tex](k \:-\: 1)d \;=\; \sum_{i=1}^{k-1} a_{i+1} \:-\: a_i \;=\; a_k \:-\: a_1,[/tex]
som gir
[tex]d \;=\; \frac{a_k \:-\: a_1}{k \:-\: 1} \;=\; \frac{(n-1) \:-\: 1}{\phi(n) \:-\: 1} \;=\; \frac{n \:-\: 2}{\phi(n) \:-\: 1},[/tex]
dvs. at
[tex](1) \;\; (\phi(n) \:-\: 1)d \:=\: n \:-\: 2.[/tex]
Anta at [tex]p[/tex] er et primtallsfaktor i [tex]d.[/tex] Herav følger at [tex]p|n-2[/tex] fordi [tex]p|d[/tex] og [tex]d|n-2[/tex] ifølge identiteten (1).
Dermed får vi følgende rekke av implikasjoner:
[tex]p|d \;\; \Rightarrow \;\; p \leq d \;\; \Rightarrow \;\; 1 = a_1 \:<\: p \:<\: d+1 = a_2 \;\; \Rightarrow \;\; SFD(n,p) \:>\: 1 \;\; \Rightarrow \;\; p|n \;\; \Rightarrow \;\; p|n - (n-2) \;\; \Rightarrow \;\; p|2 \;\; \Rightarrow \;\; p=2.[/tex]
Altså må [tex]d = 2^m[/tex]for et heltall [tex]m \geq 2.[/tex] Følgelig blir [tex]a_2 = 2^m + 1 \:>\: 2^2 = 4 \:>\: 3,[/tex]dvs. at [tex]SFD(n,3)\:>\:1[/tex]. M.a.o. vil [tex]3|n.[/tex] Dette betyr igjen at [tex]a_2[/tex] og [tex]a_3[/tex] ikke delelig med 3, så [tex]a_2 \cdot a_3[/tex] er ikke delelig med 3. Men nå er
[tex]a_2 \cdot a_3 \:=\: (2^m \:+\: 1)(2^{m+1}\:+\: 1) \:=\: 2^{2m+1} \:+\: 3 \cdot 2^m \:+\: 1 \: \equiv \: 2 \cdot 4^{m} \:+ \: 1 \: \equiv \: 2 \cdot 1^{m} \:+ \: 1 \:= \: 3 \: \equiv \: 0[/tex] (mod 3),
så [tex]3|a_2 \cdot a_3.[/tex] Denne motsigelsen fullfører beviset.
[tex](k \:-\: 1)d \;=\; \sum_{i=1}^{k-1} a_{i+1} \:-\: a_i \;=\; a_k \:-\: a_1,[/tex]
som gir
[tex]d \;=\; \frac{a_k \:-\: a_1}{k \:-\: 1} \;=\; \frac{(n-1) \:-\: 1}{\phi(n) \:-\: 1} \;=\; \frac{n \:-\: 2}{\phi(n) \:-\: 1},[/tex]
dvs. at
[tex](1) \;\; (\phi(n) \:-\: 1)d \:=\: n \:-\: 2.[/tex]
Anta at [tex]p[/tex] er et primtallsfaktor i [tex]d.[/tex] Herav følger at [tex]p|n-2[/tex] fordi [tex]p|d[/tex] og [tex]d|n-2[/tex] ifølge identiteten (1).
Dermed får vi følgende rekke av implikasjoner:
[tex]p|d \;\; \Rightarrow \;\; p \leq d \;\; \Rightarrow \;\; 1 = a_1 \:<\: p \:<\: d+1 = a_2 \;\; \Rightarrow \;\; SFD(n,p) \:>\: 1 \;\; \Rightarrow \;\; p|n \;\; \Rightarrow \;\; p|n - (n-2) \;\; \Rightarrow \;\; p|2 \;\; \Rightarrow \;\; p=2.[/tex]
Altså må [tex]d = 2^m[/tex]for et heltall [tex]m \geq 2.[/tex] Følgelig blir [tex]a_2 = 2^m + 1 \:>\: 2^2 = 4 \:>\: 3,[/tex]dvs. at [tex]SFD(n,3)\:>\:1[/tex]. M.a.o. vil [tex]3|n.[/tex] Dette betyr igjen at [tex]a_2[/tex] og [tex]a_3[/tex] ikke delelig med 3, så [tex]a_2 \cdot a_3[/tex] er ikke delelig med 3. Men nå er
[tex]a_2 \cdot a_3 \:=\: (2^m \:+\: 1)(2^{m+1}\:+\: 1) \:=\: 2^{2m+1} \:+\: 3 \cdot 2^m \:+\: 1 \: \equiv \: 2 \cdot 4^{m} \:+ \: 1 \: \equiv \: 2 \cdot 1^{m} \:+ \: 1 \:= \: 3 \: \equiv \: 0[/tex] (mod 3),
så [tex]3|a_2 \cdot a_3.[/tex] Denne motsigelsen fullfører beviset.