1) Et Carmichaeltall [tex]n[/tex] er et sammensatt tall slik at [tex]a^n \equiv a (\rm{mod} n)[/tex] for alle tall [tex] a[/tex]. Den deler altså denne egenskapen med primtall.
Vis at dersom [tex]n[/tex] er kvadratfri (dvs ingen kvadrater deler [tex]n[/tex]), og at hvis [tex]p[/tex] er et primtall:
[tex]p|n \Rightarrow p-1|n-1[/tex]
så er [tex]n[/tex] enten et primtall eller et Carmichaeltall.
2) Finn en [tex]p[/tex] slik at [tex]7 \cdot 23p[/tex] er et Carmichaeltall.
NB: Programmering er ikke tillatt!
Carmichaeltall
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Siden [tex]n[/tex] er kvadratfri har vi at [tex]n=\prod _{i=1}^m p_i[/tex], der [tex] p_i[/tex] er distinkte primtall. Vi har så for alle tall a som ikke deles av [tex]p_j[/tex] [tex]a^n = a \cdot a^{n-1} = a \cdot a^{k(p_j-1)} \equiv a \cdot 1^k = a (\rm{mod} p_j )[/tex] for alle primtall [tex]p_j[/tex] som deler [tex]n[/tex] av betingelsen i oppgaven, der vi ved kongruenstegnet brukte Fermats lille sats.
Dersom [tex]p_j[/tex] deler [tex]a[/tex] har vi opplagt også at [tex]a^n \equiv 0 \equiv a (\rm{mod} p_j )[/tex], så kongruensen holder for alle heltall [tex]a[/tex] og alle primtall som deler [tex]n[/tex]. [tex] p_i [/tex] opplagt er relativt primiske har vi av det kinesiske restteoremet at [tex]a^n \equiv a (\rm{mod} ( p_1 p_2 p_3 \ldots p_m =n ) )[/tex] for alle heltall [tex]a[/tex].
Dette betyr at [tex]n[/tex] enten er et primtall eller et Carmichaeltall, da [tex]a^n \equiv a ( \rm {mod} n )[/tex] for alle heltall [tex]a[/tex], som var det vi ønsket å vise. Vi legger også merke til at vi har ekvivalens her, dvs at dersom [tex]n[/tex] er et Carmichaeltall og [tex]p[/tex] er et primtall som deler [tex]n[/tex] vil [tex]p-1|n-1[/tex]. Dette kan vi vise ved å la [tex]a[/tex] være et heltall som ikke er delelig med [tex]p[/tex] (som er et primtall som deler [tex]n[/tex]) og som er slik at [tex]p-1[/tex] er det minste positive heltallsverdien av [tex]b[/tex] slik at [tex]a^b \equiv 1 (\rm{mod} p)[/tex], og la [tex]n-1\equiv r ( \rm{mod} p-1)[/tex].
Vi har da at [tex]a \equiv a^{kp} = a \cdot a^{n-1} = a \cdot a^{m(p-1) + r} \equiv a \cdot a^{r} (\rm{mod} p)[/tex], som siden [tex]a^{-1}[/tex] eksisterer modulo [tex]p[/tex] ([tex](a,p)=1[/tex]) gir at [tex]a^r\equiv 1(\rm{mod} p)[/tex]. Men vi har [tex]0 \leq r <p-1[/tex], så av måten vi valgte [tex]a[/tex] på er [tex]r=0[/tex], så [tex]p-1|n-1[/tex]. (Noe kronglete, men forhåpentligvis gyldig.)
EDIT: Glemte å svare på den andre oppgaven. Vi ser at vi må ha (dersom p er et primtall) [tex]p-1 | 7 \cdot 23 \cdot p - 1[/tex], som gir at [tex]p-1|160[/tex]. Vi kan altså prøve oss frem med alle divisorer av 160 som er èn mindre enn et primtall og se om noen av dem gjør at [tex]7 \cdot \23 \cdot p [/tex] er et Carmichaeltall (som vi kan finne ut ved å bruke det vi viste i oppgaven) og få at [tex]p=41[/tex] er løsning.
Dersom [tex]p_j[/tex] deler [tex]a[/tex] har vi opplagt også at [tex]a^n \equiv 0 \equiv a (\rm{mod} p_j )[/tex], så kongruensen holder for alle heltall [tex]a[/tex] og alle primtall som deler [tex]n[/tex]. [tex] p_i [/tex] opplagt er relativt primiske har vi av det kinesiske restteoremet at [tex]a^n \equiv a (\rm{mod} ( p_1 p_2 p_3 \ldots p_m =n ) )[/tex] for alle heltall [tex]a[/tex].
Dette betyr at [tex]n[/tex] enten er et primtall eller et Carmichaeltall, da [tex]a^n \equiv a ( \rm {mod} n )[/tex] for alle heltall [tex]a[/tex], som var det vi ønsket å vise. Vi legger også merke til at vi har ekvivalens her, dvs at dersom [tex]n[/tex] er et Carmichaeltall og [tex]p[/tex] er et primtall som deler [tex]n[/tex] vil [tex]p-1|n-1[/tex]. Dette kan vi vise ved å la [tex]a[/tex] være et heltall som ikke er delelig med [tex]p[/tex] (som er et primtall som deler [tex]n[/tex]) og som er slik at [tex]p-1[/tex] er det minste positive heltallsverdien av [tex]b[/tex] slik at [tex]a^b \equiv 1 (\rm{mod} p)[/tex], og la [tex]n-1\equiv r ( \rm{mod} p-1)[/tex].
Vi har da at [tex]a \equiv a^{kp} = a \cdot a^{n-1} = a \cdot a^{m(p-1) + r} \equiv a \cdot a^{r} (\rm{mod} p)[/tex], som siden [tex]a^{-1}[/tex] eksisterer modulo [tex]p[/tex] ([tex](a,p)=1[/tex]) gir at [tex]a^r\equiv 1(\rm{mod} p)[/tex]. Men vi har [tex]0 \leq r <p-1[/tex], så av måten vi valgte [tex]a[/tex] på er [tex]r=0[/tex], så [tex]p-1|n-1[/tex]. (Noe kronglete, men forhåpentligvis gyldig.)
EDIT: Glemte å svare på den andre oppgaven. Vi ser at vi må ha (dersom p er et primtall) [tex]p-1 | 7 \cdot 23 \cdot p - 1[/tex], som gir at [tex]p-1|160[/tex]. Vi kan altså prøve oss frem med alle divisorer av 160 som er èn mindre enn et primtall og se om noen av dem gjør at [tex]7 \cdot \23 \cdot p [/tex] er et Carmichaeltall (som vi kan finne ut ved å bruke det vi viste i oppgaven) og få at [tex]p=41[/tex] er løsning.