8.1 Bevis- og føringsstandarden + utenat-banken

(i) Divisjonskjeden frem, linje for linje, til rest $0$. Siste ikke-null rest er $\gcd(a,b)$.
(ii) Substitusjonskjeden baklengs, fra nest siste linje og oppover, til du står med
$$\gcd(a,b)=ax+by.$$
(iii) Konklusjonssetningen: «altså er $\gcd(a,b)=a\cdot x+b\cdot y$.»

Gcd alene, uten Bézout-koeffisientene, gir trekk — og verre: det stopper resten av oppgaven, for både den diofantiske løsningen, den modulære inversen og RSA-eksponenten $d$ leses ut av kjeden baklengs, ikke ut av gcd-en.

Den utvidede algoritmen i tabellform er en fullgod alternativ føring, aldri en erstatning for at koeffisientene vises.

(må sitte utenat — malen er en form, og under kode D finnes ingen mal å slå opp i)

Ved diofantiske likninger, lineære kongruenser og kongruenssystemer kommenteres løsbarheten som en setning, før du løser. Malen er ordrett den samme i hele boka:

- diofantisk likning $ax+by=c$: «fordi $d=\gcd(a,b)$ deler $c$, har likningen løsninger»;
- lineær kongruens $ax\equiv b\pmod m$: «siden $d=\gcd(a,m)$ deler $b$, er kongruensen løsbar, og den har $d$ inkongruente løsninger modulo $m$»;
- kongruenssystem: «modulene er parvis relativt primiske, så systemet har ved det kinesiske restteoremet nøyaktig én løsning modulo $M$».

Setningen er verdt poeng i seg selv, og den koster ti sekunder. Er kriteriet ikke oppfylt, er den hele svaret: «$d\nmid c$, altså finnes ingen heltallsløsninger» — og du er ferdig med delpunktet.

(må sitte utenat)

- Diofantisk likning: full parametrisering
$$x=x_0+\frac bd t,\qquad y=y_0-\frac ad t,\qquad t\in\mathbb{Z}.$$
- Lineær kongruens: alle $d$ inkongruente løsninger modulo $m$, med avstand $m/d$.
- Kongruenssystem: svaret som en restklasse med periode, $x\equiv x_0\pmod M$ — ikke bare tallet $x_0$.
- Kvadratisk kongruens: «to løsninger, $x\equiv\pm x_0$» eller «ingen løsning».

Og: «minste positive» besvares eksplisitt når det spørres om, med både $x$ og $y$ regnet ut. Det er det delpunktet som oftest mistes helt på slutten av en ellers korrekt besvarelse.

(må sitte utenat)

Store potenser modulo $n$ føres i sju steg, ordrett som i kap. 2.1 og kap. 2.6:

(i) faktoriser modulusen; (ii) skriv $\gcd$-sjekken som en setning; (iii) regn ut $\phi(n)$ (eller les $p-1$ for primtallsmodulus); (iv) reduser eksponenten modulo $\phi(n)$ eller $p-1$, med teoremnavnet; (v) binærutviklingen av eksponenten og kvadrattabellen; (vi) sett sammen produktet, to faktorer av gangen; (vii) konklusjon, med svaret i $0,\dots,n-1$.

Steg (ii) er det som avgjør om steg (iv) i det hele tatt er lovlig, og steg (v) er det som viser at du regnet det selv. Et sluttall uten kvadrattabell er et sluttall uten metode.

(må sitte utenat)

Bærer et teorem argumentet, skal navnet stå i setningen. Fasitene i arkivet gjør det rutinemessig, og formuleringene er faste:

«ved Euklids algoritme» · «etter Bézout» · «ved det kinesiske restteoremet» · «fra Fermats lille teorem» · «fra Eulers teorem» · «ved Wilsons teorem» · «etter aritmetikkens fundamentalteorem» · «ved Euklids lemma» · «etter den kvadratiske resiprositetsloven» · «ved Eulers kriterium» · «ved induksjonsprinsippet».

Grunnen er ikke seremoniell. Navnet er stedet der vilkåret bor: sier du «fra Eulers teorem», har du samtidig sagt at $\gcd(a,n)=1$ er sjekket; sier du «ved Wilsons teorem», har du sagt at modulusen er et primtall. Et argument uten teoremnavn er et argument uten vilkårssjekk.

(må sitte utenat — de elleve formuleringene er hele listen)

Trinn 1 — svaret. Sluttallet, riktig. Alene teller det lite: instruksen på hvert sett er at alle svar skal begrunnes.

Trinn 2 — regningen. Mellomstegene som fører til svaret: divisjonskjeden, kvadrattabellen, reduksjonskjeden. Dette er det de fleste husker å skrive.

Trinn 3 — rammen rundt regningen. Vilkåret kommentert før du regner ($\gcd$-sjekken, $d\mid c$, parvis primiskhet, «$p$ er et primtall»), teoremnavnet der argumentet hviler, konklusjonen som en setning, og svaret komplett (hele mengden / alle løsningene / alle tilfellene).

Trinn 3 er det som skiller en besvarelse som «har regnet riktig» fra en som er ferdig. Den koster ti–tjue sekunder per delpunkt, og den er den billigste karakterøkningen i hele faget.

(må sitte utenat — de tre trinnene er selvsjekken du kjører på hvert delpunkt før du blar videre)

Ordene i oppgaveteksten peker nesten alltid entydig på sjangeren, og du kan lære listen:

- «i hele tall» / «samtlige løsninger» ⇒ diofantisk likning (A)
- «alle inkongruente løsninger» / «invers modulo» ⇒ lineær kongruens (B)
- to eller flere kongruenser samtidig / «det minste tallet som gir rest … og rest …» ⇒ kinesisk restteorem (C)
- «offentlig nøkkel» / «krypter» / «dekrypter» ⇒ RSA (D)
- «finn resten når … deles på …», særlig med fakultet eller stor eksponent ⇒ restberegning (E)
- «har $x^2\equiv a\pmod p$ løsning» / «kvadratisk rest» ⇒ Legendre (F)
- «minste $k$ med $a^k\equiv 1$» / «primitiv rot» ⇒ orden (G)
- «antall divisorer» / «summen av divisorene» / «minste $n$ med» ⇒ $\tau$ og $\sigma$ (H)
- «vis at … er delelig med» / «er sammensatt» / «uendelig mange primtall» ⇒ delelighetsbevis (I)
- «for alle $n\ge n_0$» ⇒ induksjon (J)
- «kjedebrøk» / «konvergent» / «$x^2-Dy^2=1$» / «pytagoreisk trippel» ⇒ spesialtema (K)

To signalord som lurer: «finn resten» med en liten eksponent er ren kongruensregning, ikke sjanger E — reduser og bli ferdig. Og «vis at» foran en tallpåstand (ikke en allpåstand) er ofte bare en utregning: «vis at $7$ er en primitiv rot modulo $13$» er sjanger G, ikke et bevis i sjanger I.

(må sitte utenat — dette er metodevalget, og det er ikke noe du kan slå opp under kode D)

Fire timer, omtrent ti likt vektede delpunkt: 24 minutter per delpunkt, med den fordelingen at de mekaniske sjangrene tar mindre og bevisoppgaven tar mer.

Et realistisk budsjett, målt på oppgavetypene i denne boka:

Ikke løs settet fra oppgave 1 til oppgave 8 i rekkefølge. Kjør tre runder:

Runde 1 (~5 min, ingen regning). Les hele settet. Skriv sjangerbokstaven i margen ved hvert delpunkt. Marker de tre du er sikrest på.

Runde 2 (~2,5 timer). Ta de sikre først, i økende vanskelighet. Grunnen er ikke psykologisk, den er aritmetisk: alle delpunkt teller likt, så et delpunkt du tar på tolv minutter er verdt like mye som et du bruker førti på. Å ta de billige først maksimerer antall ferdige delpunkt per time.

Runde 3 (~40 min). De vanskelige, med det du har lært av de andre. Ofte har delpunkt i samme oppgave felles $\phi(n)$, felles faktorisering eller felles gcd — regnet du den i a), er den gratis i c).

Sett av de siste 20 minuttene til kontroll, ikke til et nytt delpunkt. En funnet regnefeil er verdt mer enn en halv ny oppgave.

(må sitte utenat — dette er hele eksamensstrategien, og den kan ikke leses fra et ark du ikke har med deg)

Står du fast, forlater du delpunktet. Men ikke tomt. Tre linjer, alltid, før du blar videre:

1. Sjangeren og metoden: «dette er en kvadratisk kongruens; jeg skal regne $\displaystyle \left(\frac{a}{p}\right)$ med resiprositetsloven».
2. Vilkåret eller oppsettet: det du faktisk har fått til — faktoriseringen, $\phi(n)$, $\gcd$-en, de to første linjene i divisjonskjeden.
3. Der du stoppet: «her trenger jeg inversen til $24$ modulo $89$, som jeg ikke fikk til».

Grunnen er enkel: delpunktene er selvstendige og teller likt, men innenfor ett delpunkt gis uttelling for metode. Tre linjer riktig oppsett er langt fra null.

Og motsatt: oppgi aldri et sluttall du ikke har regnet. Et gjettet tall uten metode gir ingenting og koster tid du kunne brukt på neste delpunkt.

(må sitte utenat — regelen brukes under tidspress, og det er nettopp da den glemmes)

(2) Induksjonshypotese. Som egen linje, med innholdet skrevet ut: «anta at $P(k)$ holder for en $k\ge n_0$, altså at [påstanden for $k$].»

(3) Induksjonssteg. Utled $P(k+1)$, og skriv setningen

«Her bruker vi induksjonshypotesen:»

nøyaktig der innsettingen skjer. Avslutt med «ved induksjonsprinsippet holder $P(n)$ for alle $n\ge n_0$.»

De to setningene som må stå, er hypotesen (steg 2) og «her bruker vi induksjonshypotesen» (steg 3). De er de to stedene en leser kontrollerer at beviset faktisk er et induksjonsbevis og ikke en omskrivning.

Antall basissteg = antall ledd rekursjonen ser tilbake. Bruker steget både $P(k)$ og $P(k-1)$, trengs to basissteg (sterk induksjon).

(må sitte utenat)

Skal en påstand vises for alle hele tall, og argumentet går via rester modulo $m$, skal alle $m$ restene stå der — hver som en merket linje:

«Tilfelle $n\equiv 0\pmod 3$: …» · «Tilfelle $n\equiv 1\pmod 3$: …» · «Tilfelle $n\equiv 2\pmod 3$: …»

Grunnlaget er divisjonsalgoritmen: hvert helt tall har nøyaktig én rest $r$ med $0\le r<m$, så de $m$ tilfellene dekker alt. En case-analyse som hopper over en rest, beviser ingenting — og et tilfelle som «åpenbart ikke kan skje», skal utelukkes med en setning, ikke ved stillhet.

Valget av modulus er hele trikset: velg den $m$ som gjør at kvadratene (eller potensene) i påstanden får få mulige verdier. $n^2\equiv 0,1\pmod 3$; $n^2\equiv 0,1\pmod 4$; $n^2\equiv 1\pmod 8$ for odde $n$.

(må sitte utenat — både formen og de tre kvadratrest-listene)

(2) Regn videre til noe umulig.

(3) Avslutt med en klar umulighetssetning: «men da er $q$ både et primtall og sammensatt — motsigelse», eller «men $10\nmid 5$, og det er umulig». Ikke la beviset renne ut i en observasjon.

(4) Konkluder: «antagelsen kan derfor ikke holde, og påstanden er bevist. $\blacksquare$»

Malen bærer tre av bokas sjangre: irrasjonalitet (kap. 7.3), uendelig mange primtall av en gitt form (kap. 6.3), og likninger uten heltallsløsninger (kap. 6.1).

(må sitte utenat)

Ni spørsmål, i denne rekkefølgen — de tre første er de som oftest gir treff:

1. Er Euklid ført baklengs, der oppgaven trengte Bézout-koeffisienter, en invers eller $d$ i RSA?
2. Er løsbarheten kommentert før løsningen — $d\mid c$, $d\mid b$, parvis primiskhet?
3. Står hele løsningsmengden der — alle $d$ restklassene, $t$-parametriseringen, perioden i CRT-svaret — og er «minste positive» besvart der det ble spurt?
4. Er $\gcd$-sjekken skrevet før Eulers teorem ble brukt?
5. Er Wilson-fortegnene riktige — $j$ manglende faktorer gir koeffisienten $(-1)^j\cdot j!$?
6. Er fortegnsfaktoren i resiprositetsloven regnet, ikke gjettet — og er supplementsreglene brukt med riktig modulus ($4$ for $(-1/p)$, $8$ for $(2/p)$)?
7. Er alle restene dekket i hver case-analyse?
8. Er basissteget skrevet i hvert induksjonsbevis, med riktig $n_0$?
9. Er teoremet navngitt der argumentet hviler på det?

Og til slutt, det tiende som ikke er et spørsmål men en sjekk: ligger hvert sluttsvar i $0,\dots,n-1$? Et negativt eller for stort svar på en restberegning er nesten alltid en glemt siste reduksjon.

(må sitte utenat — dette er kontrolltiden din, og lista finnes ikke på arket)

Substitusjonskjeden baklengs: start i nest siste linje, substituer oppover, til
$$\gcd(a,b)=ax+by.$$

Bézouts identitet: $\gcd(a,b)$ er den minste positive verdien $ax+by$ kan ha.

Kontroll: sett $x$ og $y$ inn og se at du får $\gcd$-en, ikke noe annet.

(prosedyren må sitte utenat; koeffisientene $x,y$ utledes på stedet — de finnes ikke utenat for noe tallpar, og leses ut av kjeden hver gang)

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

Eulers teorem: er $\gcd(a,n)=1$, så er $a^{\phi(n)}\equiv 1\pmod n$.

Brukt som verktøy: reduser eksponenten modulo $\phi(n)$ — ikke modulo $n$.

(begge formler og teoremet med vilkåret må sitte utenat; den generelle formen $\displaystyle \phi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$ utledes på stedet av $\phi(p^k)$ pluss multiplikativiteten, to linjer)

Form 2: er $p$ et primtall, så er $a^p\equiv a\pmod p$ for alle hele tall $a$ — ingen vilkår.

Brukt som verktøy: ved primtallsmodulus reduseres eksponenten modulo $p-1$.

(begge former må sitte utenat — men om formen glipper: Fermat utledes på stedet av Euler, siden $\phi(p)=p-1$ for et primtall. Én linje, under et halvt minutt.)

Trikset på $k\cdot m!\bmod p$: skriv $(p-1)!=m!\cdot(m+1)\cdots(p-1)$, bytt hver manglende faktor med en negativ rest ($p-j\equiv -j$), og gang med inversen til koeffisienten — aldri «del».

Fortegnsregelen: med $j$ manglende faktorer er koeffisienten $(-1)^j\cdot j!$.

(teoremet og fortegnsregelen må sitte utenat; $(p-2)!\equiv 1\pmod p$ utledes på stedet på én linje, og invers-parringen er minnekroken når teoremet nøler)

Formelen: $N_k=M/m_k$; løs $N_kx_k\equiv 1\pmod{m_k}$; sett
$$x\equiv\sum_k b_kN_kx_k\pmod M.$$

Suksessiv innsetting: $x=b_1+m_1t$, sett inn i neste kongruens, løs for $t$, gjenta. Begge veier gir full uttelling — og under kode D er innsetting sikkerhetsnettet, fordi den ikke krever at noen formel sitter.

Ikke parvis primiske moduler: løsbar nøyaktig når $\gcd(m_1,m_2)$ deler $b_1-b_2$; perioden er da $\operatorname{lcm}$, ikke produktet.

(formelen og vilkåret må sitte utenat; innsettingsveien er ren kongruensregning og utledes på stedet)

Offentlig nøkkel $(n,e)$; privat $d$. Kryptering $c\equiv m^e\pmod n$, dekryptering $m\equiv c^d\pmod n$.

Den raske dekrypteringsveien: regn $c^{d\bmod(p-1)}\bmod p$ og $c^{d\bmod(q-1)}\bmod q$, og sett sammen med det kinesiske restteoremet. Fullgod, og ofte raskere for hånd.

(oppsettet må sitte utenat; korrektheten $(m^e)^d\equiv m\pmod n$ utledes på stedet fra $ed=1+k\phi(n)$ pluss Eulers teorem — tre linjer, pluss to for tilfellet $p\mid m$)

Periodisitet: $\displaystyle a\equiv b\pmod p\Rightarrow\left(\frac ap\right)=\left(\frac bp\right)$ — reduser alltid telleren først.

Fullstendig multiplikativitet: $\displaystyle \left(\frac{ab}{p}\right)=\left(\frac ap\right)\left(\frac bp\right)$ — så kvadrater i telleren faller bort.

Eulers kriterium: $\displaystyle \left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p$.

Antall løsninger av $x^2\equiv a$: to (som $\pm x_0$) om symbolet er $1$, ingen om det er $-1$.

(alt dette må sitte utenat; at det finnes $(p-1)/2$ kvadratiske rester og at $\displaystyle \sum_{a=1}^{p-1}\left(\frac ap\right)=0$ utledes på stedet av multiplikativiteten, to linjer)

Supplement 1: $\displaystyle \left(\frac{-1}{p}\right)=1$ om $p\equiv 1\pmod 4$, ellers $-1$. (Modulus 4.)

Supplement 2 — «8-regelen»: $\displaystyle \left(\frac 2p\right)=1$ om $p\equiv\pm 1\pmod 8$, ellers $-1$. (Modulus 8.)

Reduksjonsalgoritmen: reduser telleren · faktoriser · splitt med multiplikativiteten · behandle $-1$ og $2$ med supplementene · snu de odde primtallene med loven · gjenta til alt er $\pm 1$.

(loven med fortegnsfaktoren og begge supplementer må sitte utenat; supplementet for $(-1/p)$ kan i tillegg utledes på stedet fra Eulers kriterium — én linje)

Ordenslemmaet: $a^t\equiv 1\pmod n\iff\operatorname{ord}_n(a)\mid t$. Spesielt $\operatorname{ord}_n(a)\mid\phi(n)$.

Divisortesten: regn $\phi(n)$, og test divisorene i stigende rekkefølge; første treff er ordenen. Å vise at den er den minste, er en del av svaret.

Brukt som verktøy: reduser eksponenter modulo ordenen — den er ofte mye mindre enn $\phi(n)$.

(lemmaet begge veier må sitte utenat; $\operatorname{ord}(a^k)=\operatorname{ord}(a)/\gcd(k,\operatorname{ord}(a))$ utledes på stedet av lemmaet, to linjer)

En primitiv rot modulo $n$ er et element av orden $\phi(n)$; potensene treffer da alle restene som er relativt primiske til $n$.

Eksistens: nøyaktig for $n=2,\ 4,\ p^k,\ 2p^k$ med $p$ odde primtall.

Antall: $\phi(\phi(n))$.

Primdivisortesten: $a$ er primitiv rot $\iff a^{\phi(n)/q}\not\equiv 1\pmod n$ for hver primdivisor $q$ i $\phi(n)$. Én test per primdivisor — ikke per divisor.

Antall elementer av orden $d$ (når en primitiv rot finnes, og $d\mid\phi(n)$): $\phi(d)$.

(eksistens, antall og testen må sitte utenat; at alle primitive røtter er $r^k$ med $\gcd(k,\phi(n))=1$ utledes på stedet av ordensformelen for potenser, to linjer)

Begge er multiplikative for relativt primiske faktorer.

Minste $n$ med gitt $\tau(n)=m$: faktoriser $m$ på alle måter som produkt av heltall $>1$, tolk hver faktorisering som eksponentmønster $(k_i+1)$, og legg de største eksponentene på de minste primtallene. Regn ut alle kandidatene og velg den minste.

Identiteter: $\tau(n)$ er odde nøyaktig når $n$ er et kvadrattall; $\dfrac{\sigma(n)}{n}=\sum_{d\mid n}\dfrac 1d$.

($\tau$-formelen må sitte utenat; $\sigma$-formelen utledes på stedet fra den geometriske summen $1+p+\dots+p^k$ — én linje per primtallspotens)

Hver betingelse har sin jobb: den første gir positive sider, den andre gjør trippelen primitiv, den tredje hindrer at alle tre sidene blir delelige med $2$.

Faste delelighetsresultater: $4\mid x$; $3\mid xy$; $5\mid xyz$; $z\equiv 1\pmod 4$.

(parametriseringen med alle tre betingelsene må sitte utenat — å glemme paritetsbetingelsen er den belagte feilen i sjangeren; delelighetsresultatene utledes på stedet med case-analyse på $s$ og $t$, tre–fem linjer hver)

$\sqrt D$: periodisk kjedebrøk $[a_0;\overline{a_1,\dots,a_{k-1},2a_0}]$, funnet med hjelpetabellen for $m$, $d$ og $a$.

Konvergentene:
$$p_n=a_np_{n-1}+p_{n-2},\qquad q_n=a_nq_{n-1}+q_{n-2},$$
med $p_{-1}=1$, $p_{-2}=0$, $q_{-1}=0$, $q_{-2}=1$.