2.6 Drill: restberegning med de fire teoremene og CRT

Forkunnskaper

Fra boka: hele Del 2 — kap. 2.1 (Euler og $\phi$), kap. 2.2 (Fermat), kap. 2.3 (Wilson), kap. 2.4 (CRT) og kap. 2.5 (den sammensatte oppgaven). Fra Del 1 trenger du kap. 1.2 (Euklids algoritme til inverser) og kap. 1.4 (kongruensregning).

Sist du var her. De fem resultatene alle oppgavene bygger på, ferdig oppfrisket:

1. $\phi(p^k)=p^k-p^{k-1}$, og $\phi(mn)=\phi(m)\phi(n)$ når $\gcd(m,n)=1$.

2. Eulers teorem. $a^{\phi(n)}\equiv 1\pmod n$ når $\gcd(a,n)=1$ — reduser eksponenten modulo $\phi(n)$.

3. Fermats lille teorem. $a^{p-1}\equiv 1\pmod p$ når $p\nmid a$ — reduser eksponenten modulo $p-1$.

4. Wilsons teorem. $(p-1)!\equiv -1\pmod p$ — og de manglende faktorene skrives $p-j\equiv -j$.

5. Det kinesiske restteoremet. Parvis relativt primiske moduler gir én løsning modulo produktet; $N_j=M/m_j$ og $N_jx_j\equiv 1\pmod{m_j}$.

Er noe av dette usikkert, gå tilbake til kapitlet det står i før du regner oppgavene her. Drill på et usikkert fundament fester feilen i stedet for ferdigheten.

Løsningsoppskriftene

~12 minutter. Les dem, og bruk dem som referanse mens du regner oppgavene.

Fire oppskrifter dekker hele sjanger C og E. Den femte — den sammensatte — er bare de andre brukt etter hverandre.

Alle fire starter med samme spørsmål: hva er modulusen, og hva er leddet? Det er beslutningstreet fra kap. 2.5, og det avgjør hvilken oppskrift du er i.

Oppskrift 1: $a^{N}\bmod n$ i sju steg

(i) Faktoriser modulusen. Primtall eller sammensatt?

(ii) $\gcd$-sjekken. Skriv setningen «$\gcd(a,n)=1$». Er den ikke $1$, gå til oppskrift 3.

(iii) Regn ut $\phi(n)$ (eller les $p-1$ direkte for primtall).

(iv) Reduser eksponenten modulo $\phi(n)$ eller $p-1$, med teoremnavnet: «fra Eulers teorem» / «fra Fermats lille teorem».

(v) Binærutvikling og kvadrattabell — reduser etter hvert kvadrat.

(vi) Sett sammen produktet, to faktorer av gangen.

(vii) Konklusjon som en setning, svaret i $0,\dots,n-1$.

Snarvei å se etter i steg (ii)–(iii): reduser grunntallet først. Blir det $0$, $1$ eller $-1$, er oppgaven ferdig på én linje.

Oppskrift 2: $k\cdot m!\bmod p$ i fem steg

(1) Sjekk at $p$ er et primtall, og skriv Wilsons teorem: $(p-1)!\equiv -1\pmod p$.

(2) Uttrykk $(p-1)!$ ved $m!$: $(p-1)!=m!\cdot(m+1)(m+2)\cdots(p-1)$.

(3) Bytt de manglende faktorene med negative rester ($p-j\equiv -j$), og regn det lille produktet. Med $j$ manglende faktorer er koeffisienten $(-1)^{j}\cdot j!$.

(4) Gang med inversen til koeffisienten modulo $p$ — aldri «del».

(5) Gang med $k$, reduser, og konkludér.

Er modulusen sammensatt, gjelder ikke Wilson. Da er $m!\equiv 0$ hvis faktorene i modulusen står i $m!$.

Oppskrift 3: CRT — system, og splitting

A. Løs et system $x\equiv b_j\pmod{m_j}$:

(1) Sjekk parvis primiskhet, og skriv setningen.
(2) Forenkle hver kongruens til formen $x\equiv b_j$.
(3) Formelen: $M=\prod m_j$, $N_j=M/m_j$, løs $N_jx_j\equiv 1\pmod{m_j}$, og sett $x\equiv\sum b_jN_jx_j\pmod M$.
(3′) Eller suksessiv innsetting: $x=b_1+m_1t$, sett inn i neste, løs for $t$, gjenta. Begge er fullgode.
(4) Reduser modulo $M$, og kontrollér i alle kongruensene.

B. Splitt en beregning når $\gcd(a,n)\ne 1$:

(1) Faktoriser $n$ i primtallspotenser.
(2) Regn hele uttrykket modulo hver potens: er $p\mid a$ og eksponenten $\ge k$, er leddet $\equiv 0\pmod{p^k}$; ellers Euler.
(3) Sett sammen med CRT, og kontrollér.

Ikke parvis primiske moduler? Sjekk om $\gcd(m_1,m_2)$ deler $b_1-b_2$ — er det ikke slik, har systemet ingen løsning.

Oppskrift 4: den sammensatte oppgaven i seks steg

(1) Faktoriser modulusen.
(2) Del uttrykket i ledd — fakultet, potens, vanlig tall.
(3) $\gcd$-sjekk for hvert potensledd. Ikke $1$ ⇒ oppskrift 3B.
(4) Reduser hvert ledd med sitt teorem (oppskrift 1 eller 2).
(5) Kombiner restene slik uttrykket sier, og reduser modulo $n$.
(6) Konkludér.

Arbeidsvanen som forebygger den vanligste feilen: to kolonner på arket, én per ledd, som møtes først i siste linje.

— naturlig pausepunkt —

De fem kontrollpunktene

Under kode D er selvkontroll den eneste kontrollen du har — det finnes ingen fasit i rommet og ingenting å slå opp i. Disse fem tar til sammen under to minutter og fanger nesten alt.

Gjennomregnet eksamenscase

~15 minutter.

Her er en typisk oppgave av den sammensatte typen, med tre delpunkt som bygger på hverandre — nøyaktig den formen arkivet bruker. Underveis står margnotater som sier hva hvert steg er verdt, og hvorfor.

Les den én gang med blyanten i hånda, og regn deretter oppgavene selv.

Oppgavene

~55 minutter til sammen. Tretten oppgaver, gruppert etter variant.

Regn dem med penn og lukket bok. Det er den eneste treningsformen som ligner eksamen under hjelpemiddelkode D, og forskjellen mellom å ha lest en oppskrift og å kunne den, viser seg først når boka er lukket.

Gruppene: oppgave 1–4 er $a^{N}\bmod n$ (den siste med $\gcd\ne 1$), 5–7 er Wilson-fakultet, 8–10 er CRT (én med hver metode, én med ikke-primiske moduler), og 11–13 er sammensatte. Den siste er tredelt, som på eksamen.

— naturlig pausepunkt —

Prosedyrekort

Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 85 minutter gjelder oppskriftene, casen og oppgavene.

Drillkapitlene har ingen begrepsbank i vanlig forstand: begrepene står i kap. 2.1–kap. 2.5. Kortene her er oppskriftskort — de tar prosedyrene og gjør dem til noe du kan gjenkalle kaldt, som kode D krever.