23. Arytmetyka - Wstęp do matematyki 06-DPMALI0

Treści kształcenia. Arytmetyka liczb całkowitych: podzielność, NWD i NWW, algorytm Euklidesa i rozszerzony algorytm Euklidesa, liczby pierwsze i sito Eratostenesa. Kongruencje (arytmetyka modularna), odwrotność modulo $n$ , małe twierdzenie Fermata i liczby Carmichaela.

Efekty kształcenia. Potrafi wyznaczać NWD, NWW i odwrotności modulo $n$ (algorytm Euklidesa i jego rozszerzona wersja) oraz wykonywać obliczenia na kongruencjach. Potrafi stosować małe twierdzenie Fermata do wykazywania, że dana liczba jest złożona, i zna ograniczenia tego testu (liczby Carmichaela).

Liczby całkowite¶

Na tych zajęciach skupimy się na arytmetycznych własnościach liczb całkowitych. W szczególności interesować nas będzie podzielność, związki dodawania z mnożeniem i zastosowania w szczególnych działach informatyki takich jak kryptografia.

Liczby całkowite (jako zbiór) oznaczamy symbolem $\mathbb{Z}$ . Zbiór ten zawiera liczby naturalne (z zerem), których zbiór oznaczamy $\mathbb{N}$ . Liczby całkowite, które nie są naturalne, nazywamy liczbami ujemnymi.

\mathbb{Z} = \{0,1,2,3,\ldots \}\cup \{-1,-2,-3,\ldots \}.

Na zbiorze liczb całkowitych określamy dwie operacje dodawania ( $+$ ) i mnożenia ( $\cdot$ ). Obie te operacje są naturalnym rozszerzeniem analogicznych operacji zdefiniowanych na zbiorze liczb naturalnych.

Wraz z operacjami $+,\cdot$ liczby całkowite tworzą pierścień.

Podzielność¶

Mnożenie liczb całkowitych ma bardzo bogatą strukturę. Przy jego wykonywaniu ważną relacją pomiędzy liczbami całkowitymi jest podzielność.

Definicja

Liczba całkowita $a$ jest podzielna przez liczbę całkowitą $b$ , o ile istnieje liczba całkowita $c$ , które razem spełniają

a = b\cdot c

Mówimy, że $b$ jest dzielnikiem liczby $a$ , gdy zachodzi powyższa relacja. Oznaczamy ją $b\mid a$ .

Proste wnioski:

Liczba 0 jest podzielna przez dowolną liczbę całkowitą.
Liczba 1 jest dzielnikiem dowolnej liczby całkowitej.
Dla każdej liczby całkowitej $a$ zachodzi $a\mid a$ .
Jeśli $a\mid b$ oraz $b\mid a$ , wówczas $a=b$ lub $a=-b$ .
Jeśli $a\mid b$ i $a\mid c$ , to $a\mid (b+c)$ .

Największy wspólny dzielnik¶

Dla dwóch liczb całkowitych $a,b$ takich, że $(a,b)\neq (0,0)$ , największą dodatnią liczbę całkowitą, która dzieli $a$ oraz $b$ , nazywamy największym wspólnym dzielnikiem i oznaczamy $NWD(a,b)$ .

Standardowo przyjmowaną konwencją jest $NWD(0,0) = 0$ .

Zauważmy, że $NWD(a,b) = NWD(a,-b)$ oraz $NWD(a,b) = NWD(b,a)$ .

Twierdzenie (Euklides) Niech $a,b$ będą liczbami całkowitymi. Zachodzi równość

NWD(a,b) = NWD(a,a+b)

W szczególności oznacza to, że dla dowolnej liczby całkowitej $k$ zachodzi

NWD(a,b) = NWD(a,k\cdot a+b).

Mając dane dwie liczby całkowite $a,b$ , takie, że $b\neq 0$ , istnieje dokładnie jedna para liczb całkowitych $q,r$ spełniająca $0\leq r <|b|$ oraz

a = q\cdot b+r.

Liczbę $r$ nazywamy resztą z dzielenia liczby $a$ przez $b$ .

Algorytm Euklidesa¶

Powyższe twierdzenie udowodnione przez Euklidesa w księdze VII pozwala nam napisać bardzo prosty i szybki algorytm obliczenia największego wspólnego dzielnika.

Wejście: dwie liczby nieujemne $a,b$ Wyjście: największy wspólny dzielnik $a,b$ .

Algorytm:

Jeśli $b=0$ , zwróć $a$ i zakończ algorytm.
Niech $r$ będzie resztą z dzielenia $a$ przez $b$ .
Podstaw za $a$ liczbę $b$ .
Podstaw za $b$ liczbę $r$ .
Wróć do kroku 1.

def NWD(a,b):
    a=abs(a) #liczby nieujemne
    b=abs(b)
    while b!=0: #dopóki b jest różne od 0, wykonuj pętlę
        r = a%b #reszta z dzielenia a przez b
        a = b
        b = r
    return a

NWD(15,19)

1

Zadanie 1 (NWD)¶

Oblicz największy wspólny dzielnik liczb $2^{100}+1$ i 2¹⁰⁰. Czy do tego celu musisz wyznaczyć wszystkie cyfry dziesiętne obu liczb?

Najmniejsza wspólna wielokrotność¶

Dla dwóch liczb całkowitych $a,b$ niezerowych najmniejszą dodatnią liczbę całkowitą, która jest podzielna przez $a$ oraz $b$ , nazywamy najmniejszą wspólną wielokrotnością i oznaczamy $NWW(a,b)$ . Liczba taka zawsze istnieje, bo $|ab|$ jest dodatnią liczbą podzielną przez $a$ oraz $b$ . Ponadto jest ona dzielnikiem $ab$ . Zachodzi równość

|ab| = NWD(a,b)\cdot NWW(a,b).

Liczby całkowite, dla których $NWD(a,b)=1$ , nazywamy względnie pierwszymi.

Liczby pierwsze¶

W zbiorze liczb całkowitych z relacją podzielności $\mid$ wyróżniamy pewien szczególny podzbiór liczb, które mają mało dzielników.

Definicja

Niech $n$ będzie liczbą całkowitą większą niż 1. Liczba $n$ jest liczbą pierwszą, gdy jedynymi jej dodatnimi dzielnikami są 1 oraz $n$ .

Twierdzenie

Niech $N$ będzie liczbą naturalną. Istnieje algorytm, który zwraca $N$ różnych liczb pierwszych.

Dowód

Dowód tego twierdzenia można zrealizować na bardzo wiele sposobów. Omówimy sobie jeden, który pochodzi (ponownie) od Euklidesa.

Zaczynamy od $N=1$ . Wówczas liczba 2 jest pierwsza i zwracamy zbiór $P_{1} = \{2\}$ .

Dla małych wartości $N$ możemy poszukiwać kolejnych liczb pierwszych, ale takie przeszukiwanie nie daje gwarancji, że znajdziemy $N$ liczb pierwszych dla każdego $N$ .

Zastosujemy następujący trik. Mając dany zbiór $P_{N}= \{p_1,\ldots p_N\}$ składający się z $N$ różnych liczb pierwszych, rozważamy liczbę

m = p_1\cdot\ldots\cdot p_N +1.

Liczba $m$ jest większa od 1 oraz jest względnie pierwsza z każdą z liczb $p_i$ . Oznacza to, że albo sama jest liczbą pierwszą, gdy ma dokładnie dwa dodatnie dzielniki, albo jest liczbą złożoną.

Gdy jest liczbą złożoną, wówczas musi mieć dwa nietrywialne dzielniki i postać $m= m_1\cdot m_2$ , gdzie $1 < m_1,m_2 < m$ . Korzystając z zasady indukcji matematycznej możemy udowodnić, że taki rozkład prowadzi do znalezienia dzielnika pierwszego $p_{N+1}$ liczby $m$ . Dzielnik ten (skoro liczby $p_i$ oraz $m$ są względnie pierwsze) jest liczbą pierwszą różną od elementów $p_i$ .

Kładziemy $p_{N+1} = m$ , gdy $m$ jest pierwsza lub $p_{N+1}$ jest dowolnym (np. najmniejszym) pierwszym dzielnikiem liczby $m$ . Tworzymy zbiór

P_{N+1} = P_{N} \cup \{p_{N+1} \}.

def najmdzielnik(n): #najmniejszy dodatni dzielnik liczby n (udowodnij, że zawsze jest liczbą pierwszą!)
    for i in range(2,floor(sqrt(n))+1):
        if n%i==0:
            return i
    else:
        return n
        
def Euklides(N):
    if N==1:
        return [2]
    else:
        c=1
        E=Euklides(N-1)
        for el in E:
            c*=el
        p=najmdzielnik(c+1)
        return E+[p]

Euklides(15) #uwaga dla dużych argumentów algorytm działa bardzo wolno

[2,
 3,
 7,
 43,
 13,
 53,
 5,
 6221671,
 38709183810571,
 139,
 2801,
 11,
 17,
 5471,
 52662739]

Zadanie 2 (podzielność iloczynu przez liczbę pierwszą)¶

Uzasadnij, że gdy liczba pierwsza $p$ dzieli iloczyn $ab$ , to dzieli $a$ lub dzieli $b$ .

Sito Eratostenesa¶

Efektywnym sposobem generowania kolejnych liczb pierwszych do zadanego górnego ograniczenia jest tzw. sito Eratostenesa. Jest to algorytm, który dla zadanej na wejściu liczby naturalnej $N$ zwraca listę wszystkich liczb pierwszych nie większych od $N$ .

Kroki algorytmu.

Wygeneruj ciąg $a = (0,0,1,\ldots, 1)$ długości $N+2$ składający się z dwóch zer i $N$ jedynek, elementy ciągu oznaczamy $a_i$ i indeksujemy je liczbami $i=0,1,\ldots$ .
Ustawiamy pozycję startową $t=2$ .
Jeśli $a_t=1$ , wówczas zwracamy na wyjście element $t$ , który jest liczbą pierwszą.
We wszystkich pozycjach o indeksach postaci $k\cdot t$ wstawiamy liczbę 0.
Zwiększamy wartość indeksu $t$ o 1.
O ile $t \leq N$ , wracamy do kroku 3. W przeciwnym przypadku kończymy algorytm.

def Sito(N):
    lpierwsze=[]
    a=[0,0]+[1]*(N)
    t=2
    while t < N:
        if a[t]==1:
            lpierwsze.append(t)
        for k in range(2,ceil(N/t)):
            a[t*k]=0
        t+=1
    return lpierwsze

Sito(40)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Zadanie 2* (wyzwanie)¶

Uzasadnij, że gdy $m\mid n$ , to $F_{m}\mid F_{n}$ .
Uzasadnij, że $NWD(F_n,F_m) = F_{NWD(n,m)}$ .
(*) Uzasadnij, że dla liczb Fibonacciego $F_{n}$ dla $n>12$ zawsze istnieje liczba pierwsza $p$ , która dzieli $F_n$ , ale nie dzieli $F_{k}$ dla żadnego $k<n$ .

Uwaga! Ostatnie zadanie jest twierdzeniem udowodnionym przez R. D. Carmichaela w 1913 roku. Praca zawierająca dowód jest dostępna tutaj.

Przeanalizuj poniższy kod algorytmu, który generuje najmniejsze nowe dzielniki pierwsze pojawiające się w ciągu Fibonacciego.

Uzasadnij, że dla każdej liczby pierwszej $p\neq 5$ liczba $F_{p+1}$ lub $F_{p-1}$ jest podzielna przez $p$ . W celu lepszego zrozumienia tego zjawiska obejrzyj odcinek serii ,,Numberphile’’ na YouTube.

def FibPierw(N):
    lp=[3]
    for i in range(4,N):
        f=fibonacci(i)
        for p in lp:
            while f%p==0:
                f/=p
        if f>1:
            q=najmdzielnik(f)
            lp.append(q)
    return lp

FibPierw(30)

Arytmetyka modularna¶

Za pomocą relacji podzielności możemy wprowadzić na liczbach całkowitych relację kongruencji. Dwie liczby całkowite $a,b$ przystają do siebie modulo $n$ , gdy zachodzi podzielność

n\mid (a-b).

Wprowadzamy nową notację

a\equiv b (\textrm{mod }n)

Podstawowe własności kongruencji¶

Relacja $\equiv$ jest relacją równoważności, tj. spełnia trzy warunki

$a\equiv a (\textrm{mod }n)$ .
$a\equiv b (\textrm{mod }n)$ implikuje $b\equiv a (\textrm{mod }n)$ .
$a\equiv b (\textrm{mod }n)$ i $b\equiv c (\textrm{mod }n)$ implikuje $a\equiv c (\textrm{mod }n)$ .

Zadanie 3 (własności kongruencji)¶

Uzasadnij korzystając z definicji relacji podzielności własności $1-3$ . Udowodnij ponadto

$a\equiv b (\textrm{mod }n)$ i $c\equiv d (\textrm{mod }n)$ implikuje $a+c\equiv b+d (\textrm{mod }n)$
$a\equiv b (\textrm{mod }n)$ i $c\equiv d (\textrm{mod }n)$ implikuje $ac\equiv bd (\textrm{mod }n)$

Rozszerzony algorytm Euklidesa¶

Dla dwóch niezerowych liczb całkowitych $a,b$ istnieją dwie inne liczby całkowite $x,y$ spełniające równanie

ax+by = NWD(a,b).

Algorytm Euklidesa, którym obliczaliśmy $NWD(a,b)$ , można rozszerzyć tak, aby wyznaczał liczby $x,y$ . Jego podstawową ideą jest przekształcanie dwóch trywialnych równań

a\cdot 1+b\cdot 0 = a

oraz

a\cdot 0+b\cdot 1 = b

poprzez dodawanie ich stronami. Po prawej stronie równania wykonując kroki jak w klasycznym algorytmie Euklidesa otrzymamy finalnie liczby 0 i $NWD(a,b)$ . Równanie, w którym prawą stroną jest $NWD(a,b)$ , będzie odpowiadało współczynnikom $x,y$ spełniającym równość $a\cdot x+b\cdot y = NWD(a,b)$ . Poniżej prezentujemy krótki kod z implementacją.

def xyNWD(a,b):
    r,r1=a,b
    s,s1=1,0 #s*a+t*b == a
    t,t1=0,1 #s1*a+t1*b == b
    while not(r1==0):
        q,r2=r//r1,r % r1
        r,s,t,r1,s1,t1=r1,s1,t1,r2,s-s1*q,t-t1*q
    d=r
    return d,s,t #s*a+t*b=d, d=GCD(a,b)

xyNWD(199,231)

(1, -65, 56)

199*(-65)+231*56

1

Zadanie 4¶

Uzasadnij, że dla dwóch kolejnych liczb Fibonacciego $a=F_{k}$ oraz $b=F_{k+1}$ algorytm xyNWD(a,b) zwróci liczby $d=1$ , $s=(-1)^k\cdot F_{k-1}$ oraz $t=(-1)^{k-1}\cdot F_{k-2}$ .

Wskazówka 1:

Udowodnij następującą tożsamość

F_{k} F_{k-1}- F_{k+1} F_{k-2}= (-1)^k

dla dowolnego $k\geq 2$ .

Wskazówka 2:

Tożsamość wynika z definicji macierzowej liczb Fibonacciego (+ własności wyznacznika macierzy 2x2).

Wskazówka 3:

Tożsamość można udowodnić korzystając z formuły Bineta.

f=lambda k: xyNWD(fibonacci(k),fibonacci(k+1))==(1,(-1)^k*fibonacci(k-1),(-1)^(k-1)*fibonacci(k-2))
[f(i) for i in range(2,10)]

[True, True, True, True, True, True, True, True]

Rozszerzony algorytm Euklidesa pozwala nam znajdować odwrotności liczb modulo $n$ . Konkretnie - mając daną liczbę $a$ oraz względnie pierwszą dodatnią liczbę całkowitą $n$ , z rozszerzonego algorytmu Euklidesa wynika, że istnieją $x,y$ całkowite spełniające równanie

ax+ny = 1

Oznacza to, że $ax\equiv 1(\textrm{mod }n)$ . Liczbę $x$ nazywamy multiplikatywną odwrotnością modulo $n$ .

Zadanie 5 (odwrotność multiplikatywna)¶

Znajdź odwrotności multiplikatywne dla liczby 2 modulo $n=3,5,7$ .

Prawo skracania¶

Jeśli mamy daną kongruencję $ax\equiv bx(\textrm{mod }n)$ i liczby $x$ oraz $n$ są względnie pierwsze, wówczas zachodzi kongruencja

a\equiv b(\textrm{mod }n).

Do udowodnienia tej własności wykorzystujemy własność 5. wraz z istnieniem odwrotności modulo $n$ dla liczby $x$ .

Małe twierdzenie Fermata¶

Dla dowolnej liczby całkowitej $n$ oraz liczby pierwszej $p$ zachodzi następująca równość

n^p\equiv n(\textrm{mod }p).

Dowód tego interesującego twierdzenia pomijamy.

Zadanie 6 (małe twierdzenie Fermata)¶

Uzasadnij, że gdy $NWD(n,p)=1$ , wówczas $n^{p-1}\equiv 1(\textrm{mod }p)$ .
Uzasadnij (przez kontrapozycję), że jeśli dla dwóch względnie pierwszych liczb $n,p$ nie zachodzi $n^{p-1}\equiv 1(\textrm{mod }p)$ , to $p$ nie jest liczbą pierwszą.
Wykorzystaj $n=2$ , aby uzasadnić, że $p=1111$ nie jest liczbą pierwszą (użyj 2).

Przy wykonywaniu potęgowania modulo $p$ najlepszy efekt uzyskamy wykonując redukcję liczby przy każdej operacji potęgowania. Ponadto stosujemy algorytm szybkiego potęgowania!

pow(2,1110,1111) #==(2**(1110))%1111 - uwaga proszę nie wyznaczać 2**1110 bez redukcji!

1024

Fermat spekulował, że liczby postaci $2^{2^n}+1$ są pierwsze dla wszystkich $n$ naturalnych. Sprawdź korzystając z testu Fermata przy podstawie 3, że oprócz czterech pierwszych wartości (które istotnie są pierwsze!) żadna z liczb Fermata dla $1\leq n\leq 12$ nie jest liczbą pierwszą.

Czy potrafisz znaleźć wszystkie dzielniki pierwsze tych liczb?

f = lambda k: pow(3,2^(2^k),2^(2^k)+1)
[f(k) for k in range(1,12)]

[1,
 1,
 1,
 1,
 3029026160,
 8752249535465629170,
 47511664169441434718291075092691853899,
 113080593127052224644745291961064595403241347689552251078258028018246279223993,
 13387457852131866017809974335626508736765841341908171621341620739066502578793457441078230804865246011339933833061458906559278633032869468345609327807927612,
 146809528970244036024821005514683473483244699825046485942988727983049278671435326268165085575181832374726912946280018892919388962699993405908818784177788470178225764936427450039582955979907044211973217849267621360435307454207055855850222255439616231847463892347771894224104545724927599853426578286430466818141,
 30182254562411366016290758815250615385119773900166287071320012103534598658748016249356706212399576409176051623391493996034124229337964810272435823998759626339401861304936841613905227081361815373560623362517120490947404339480460474313332173820677516012404946143838387043195618836260126897873905424390972879492407142873302089766617045846445406669503126391560898750223711517657699612890637345675153011392343307620981019447351020682006327614009099495824926766595975575854120577153137811068800000938167385336783270712238367290842981503683862065572101540670645762238184533792146272643893152798145446980427283893716719008826]

Uwaga!

Istnieją liczby naturalne $p$ złożone, które spełniają $n^p\equiv n(\textrm{mod }p)$ dla każdej liczby całkowitej $n$ . Takie liczby nazywamy liczbami Carmichaela.

Zadanie 7 (liczby Carmichaela)¶

Wyznacz pierwszych 5 liczb Carmichaela.

def najmdzielnik(n): #najmniejszy dodatni dzielnik liczby n (udowodnij, że zawsze jest liczbą pierwszą!)
    for i in range(2,floor(sqrt(n))+1):
        if n%i==0:
            return i
    else:
        return n
    
def JestCarm(p):
    for n in range(p):
        if not(pow(n,p,p)==n):
            return False
    return True

[k for k in range(5000) if JestCarm(k) and not(najmdzielnik(k)==k)] #sprawdzamy czy liczba k nie jest pierwsza i spełnia warunek Carmichaela

[561, 1105, 1729, 2465, 2821]

Dodatkowe zadania¶

Przeanalizuj poniższy algorytm DzienTygodnia wyznaczania dnia tygodnia w kalendarzu gregoriańskim. (0-niedziela, 1- poniedziałek, ...)
Zapoznaj się z metodą walidacji kodu ISBN.
Zapoznaj się z testem pierwszości Millera-Rabina.
Na 15 stycznia 2023 największą znaną liczbą pierwszą jest liczba Mersenna $M_{51} = 2^{82 589 933} − 1$ . Przeczytaj o projekcie GIMPS, aby przekonać się, w jaki sposób weryfikuje się pierwszość tak dużych liczb.
Niech $p$ będzie liczbą pierwszą, dla której $p^2$ dzieli $2^{p-1}-1$ . Przekonaj się, że dla $p=1093, 3511$ zachodzi taka własność. Poczytaj o hipotezie, że takich liczb pierwszych ma być nieskończenie wiele.
Rozważ następującą funkcję określoną na zbiorze liczb naturalnych dodatnich

f(n) = \left\{\begin{array}{cc} n/2 & 2\mid n\\ 3n+1 & 2\nmid n \end{array}\right.

Sprawdź dla wszystkich liczb naturalnych mniejszych od 100, że ciąg liczb $f(n), f(f(n)), \ldots$ zawsze trafia do jedynki.

Hipoteza Collatza

Udowodnij, że tak jest dla każdej liczby naturalnej.

def DzienTygodnia(year, month, day): #Sakamoto algorithm
    t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
    if month < 3:
        year -= 1
    return (year + year // 4 - year // 100 + year // 400 + t[month - 1] + day) % 7

year = 2022
month = 8
day = 31
print(gauss_day_of_week(year, month, day)) # Wyjscie: 3 (Sroda)