matematikk.net

Vis at alle tall på formen 3n+2 har en primtallsdivisor på samme form.

Mulig jeg har oversett noe åpenbart, men vet ikke helt hvordan jeg skal gå løs på denne oppgaven. Lar a=3n+2 for et heltall n. Hvis a er et primtall, er beviset ferdig. Anta derfor at a er sammensatt. Da har a en primtallsdivisor p som må være på én av formene:

3k
3k+1
3k+2

Hvis p=3k, får vi at 3k | 3n+2 som er umulig. Derfor må p være på en av de to siste formene.

Vet også at siden 3 ikke deler a, så må a^2 = 3k+1 (for en eller annen k) ved Fermats teorem. Siden p deler a, må også p dele a^2. Altså er p både en divisor i et tall på formen 3n+2 og et på formen 3n+1.

Det skal ikke være nødvendig å benytte Fermats teorem i alle fall.

Et hint: Det er trivielt at hvis a er et partall så er 2 en slik primfaktor, så vi antar at a er odde. Da leter vi etter primfaktorer p > 2 på denne formen. For hvilke k er p = 3k + 2 et gyldig slikt primtall?

EDIT: En liten .. logisk kortslutning her ja. Ignorer det som står ovenfor!

Det du kan gjøre er å se på negasjonen av det du skal vise. Dette er jo det samme som å vise at hvis alle primfaktorene til a er på form 3k+1 (3k har du vist er umulig) så vil også a være på samme form. Det kan du gjøre med enkel kongruensregning.

Alright, prøver å renskrive beviset.

Teorem: Dersom a er på formen 3n+2, så er en av primtallsdivisorene til a på samme form.

Bevis:

Hvis a er et primtall, er beviset ferdig. Anta derfor at a er sammensatt. La p være en primtallsdivisor til a. p må være på én av de tre formene:

3k
3k+1
3k+2

Hvis p=3k, vil [tex]3k \mid 3n+2[/tex] som gir 3kt = 3n+2 for en t. Dette gir igjen 3(kt-n) = 2, med andre ord [tex]3 \mid 2[/tex], en umulighet. Derfor må p være på en av formene 3k+1 eller 3k+2.

Dersom a ikke har en primtallsdivisor på formen 3k+2, er alternativet at alle primtallsdivisorene er på formen 3k+1. Anta dette, og la

[tex] a = p_1p_2 \cdots p_t[/tex]

med [tex]p_i \equiv 1 \pmod 3[/tex] for [tex]1 \leq i \leq t[/tex].

Ganger vi sammen kongruensene, får vi

[tex]p_1p_2 \cdots p_t \equiv 1^t = 1 \pmod 3[/tex]

Altså at a er på formen 3m+1. Men dette motstrider antakelsen om at a er på formen 3m+2, altså må a ha minst én primtallsfaktor på formen 3k+2.

Ser glimrende ut

Jeg vet ikke helt hva jeg tenkte til å begynne med i sted, men jeg mener å huske jeg gjorde noe annerledes enn dette en gang (syns nemlig jeg husker å ha gjort denne oppgaven tidligere. Men det kan jo godt være jeg gjorde den galt den gangen også.)