Bevis och talteori

Matematik bygger på bevis: logiska resonemang som visar att ett påstående gäller i alla fall, inte bara i de exempel man har prövat. Talteori handlar om heltalens egenskaper, som delbarhet, primtal och rester. Kapitlet tränar båda delarna: att resonera stringent och att använda egenskaper hos heltal, bland annat i kryptering och felrättande koder.

Bevis

En sats är ett påstående som har bevisats. Ett bevis är en kedja av slutsatser från definitioner och tidigare satser. Vanliga bevismetoder är direkta bevis, motsägelsebevis, bevis genom kontraposition och induktionsbevis. Ett motexempel visar att ett allmänt påstående är falskt.

Talteori

Ett primtal är ett heltal större än 1 som bara är delbart med 1 och sig självt. Varje heltal större än 1 kan skrivas som en produkt av primtal på precis ett sätt, bortsett från ordningen. Det kallas aritmetikens fundamentalsats.

Talföljder

En talföljd kan ges med en explicit formel, som $\displaystyle a_n=2n+1$, eller rekursivt, som $\displaystyle a_{n+1}=a_n+2$ med $\displaystyle a_1=3$.

• Att tro att några exempel räcker som bevis.
• Att räkna 1 som primtal.
• Att använda samma bokstav för två tal som inte behöver vara lika, till exempel skriva båda udda talen som $\displaystyle 2k+1$.