Nyttig tallteori

I enkelte deler av dette kurset vil det være en fordel om man har hatt litt elementær tallteori. Dette gjelder spesielt når vi studerer gruppen \( \mathbb{Z}_n = \{ 0,1, \dots, n-1 \} \), hvor binæroperasjonen er addisjon modulo \( n \). Her er en kort oppsummering - uten bevis - av de viktigste tallteoretiske konseptene som er nyttige for oss.

Ethvert positivt heltall \( n \ge 2 \) kan skrives som et produkt \( n = p_1^{a_1} \cdots p_t^{a_t} \) av primtall. Primtallene \( p_i \) og eksponentene \( a_i \) er unike.

La \( a \) og \( b \) være to heltall som ikke begge er null. Den største felles divisoren av disse heltallene, betegnet \( \gcd (a,b) \), er det største positive heltallet som deler dem begge. Med andre ord er \( \gcd (a,b) \) det unike positive heltallet \( d \) som tilfredsstiller følgende:

1. \( d \mid a \) og \( d \mid b \);
2. Dersom \( c \) er et heltall som deler både \( a \) og \( b \), så vil \( c \le d \).

Den største felles divisoren kan alltid uttrykkes som en lineærkombinasjon av \( a \) og \( b \): det finnes heltall \( u \) og \( v \) slik at \( d = au+bv\).

Dersom \( \gcd (a,b) =1 \), kaller vi \( a \) og \( b \) relativt primiske. Det betyr at når vi primtallsfaktoriserer de to tallene (forutsatt at \( a \ge 2 \) og \( b \ge 2 \)), så vil ikke et primtall inngå i begge faktoriseringene. Fra over vet vi da at det finnes heltall \( u \) og \( v \) slik at \( 1 = au+bv\), men det motsatte gjelder faktisk også. Med andre ord, hvis det finnes heltall \( u \) og \( v \) slik at \( 1 = au+bv\), så er \( \gcd (a,b) =1 \).

For et positivt heltall \( n \) definerer vi \( \phi (n) \) som \[ \phi (n) = \# \{ a \in \mathbb{Z} \mid 1 \le a \le n \text{ og } \gcd (a,n)=1 \} \] Med andre ord er \( \phi (n) \) lik antall \( a \in \{ 1, \dots, n \} \) med \( \gcd (a,n)=1 \). Dette er den desidert viktigste funksjonen man møter på i grunnleggende tallteori.

La oss ta et par eksempler. Hva er \( \phi (8) \)? Da må vi se på mengden \( \{ 1,2,3,4,5,6,7,8 \} \). Blant disse tallene er \( 1,3,5,7 \) relativt primiske til \( 8 \), og siden det er fire slike tall er \( \phi (8)=4 \). For å finne \( \phi (9) \), må vi se på mengden \( \{ 1,2,3,4,5,6,7,8,9 \} \). Blant disse tallene er \( 1,2,4,5,7,8 \) relativt primiske til \( 9 \), og siden det er seks slike tall er \( \phi (9)=6 \). For et primtall \( p \) er \( \phi (p)= p-1 \), siden alle de \( p-1 \) første tallene i mengden \( \{ 1, \dots, p-1, p \} \) er relativt primiske med \( p \).

La \( n \) være et positivt heltall. Når vi studerer gruppen \( \mathbb{Z}_n = \{ 0,1, \dots, n-1 \} \), bruker vi addisjon modulo \( n \), betegnet \( +_n \), som binæroperasjon. Det vi gjør da er kongruensregning modulo \( n \). For to heltall \( a \) og \( b \) skriver vi \[ a \equiv b \hspace{1mm} ( \rm{mod} \hspace{1mm} n ) \] dersom \( n \mid (a-b) \), med andre ord dersom \( n \) deler differansen \( a-b \). Vi leser dette som \( a \) er kongruent med \( b \) modulo \( n \). Dette er en ekvivalensrelasjon:

1. \( a \equiv a \hspace{1mm} ( \rm{mod} \hspace{1mm} n ) \) for alle heltall \( a \);
2. Hvis \( a \equiv b \hspace{1mm} ( \rm{mod} \hspace{1mm} n ) \), så er \( b \equiv a \hspace{1mm} ( \rm{mod} \hspace{1mm} n ) \);
3. Hvis \( a \equiv b \hspace{1mm} ( \rm{mod} \hspace{1mm} n ) \) og \( b \equiv c \hspace{1mm} ( \rm{mod} \hspace{1mm} n ) \), så er \( a \equiv c \hspace{1mm} ( \rm{mod} \hspace{1mm} n ) \).

For ethvert heltall \( a \) finnes et unikt heltall \( m_a \in \{ 0,1, \dots, n-1 \} \) med \( a \equiv m_a \hspace{1mm} ( \rm{mod} \hspace{1mm} n ) \). Binæroperasjonen \( +_n \) i gruppen \( \mathbb{Z}_n \) er nå definert ved at \[ a +_n b = m_{a+b} \] Med andre ord, for \( a,b \in \mathbb{Z}_n = \{ 0,1, \dots, n-1 \} \) definerer vi \( a +_n b \) til å være det unike tallet \( m \in \{ 0,1, \dots, n-1 \} \) med \( a+b \equiv m \hspace{1mm} ( \rm{mod} \hspace{1mm} n ) \).

Gruppen \( \mathbb{Z}_n \) er syklisk, den er blant annet generert av elementet \( 1 \in \mathbb{Z}_n \). Hvilke andre elementer i gruppen er generatorer? Jo, det er de elementene \( a \in \mathbb{Z}_n \) med \( \gcd (a,n) =1 \). Dette er en konsekvens av at \[ \gcd (a,n) =1 \Leftrightarrow \text{det finnes heltall } u,v \text{ med } 1=au+nv \] Antall generatorer i gruppen \( \mathbb{Z}_n \) er derfor \( \phi (n) \).