###### tags: `Matematyka Dyskretna M`

# Lista 4

## 1
Algorytm:
Funkcja gcd(a,b):
$\quad\quad$ Jeżeli $b==0$ to zwróć $a$
$\quad\quad$ Zwróć $gcd(b,a\space mod\space b)$

Funkcja lcm(a,b):
$\quad\quad$ Jeżeli $a==0$ to zwróć $b$
$\quad\quad$ Jeżeli $b==0$ to zwróć $a$
$\quad\quad$ Zwróć $\frac{a}{gcd(a,b)} \times b$

Z własności lcd i gcd wiemy, że $lcd(a,b)=\frac{a\times b}{gcd(a,b)}$. Wykonuję jednak w obliczeniach najpierw dzielenie przed mnożeniem, żeby nie spowodować przypadkiem overflow. Czyli jeżeli a,b,lcm(a,b) mieszczą się w określonym przedziale, to funkcja lcm(a,b) zwróci zawsze poprawny wynik.

## 2

Algorytm:
Funkcja gcd(m[k],k):
$\quad\quad$wynik <- gcd(m[0],m[1])
$\quad\quad$Powtarzaj od i=2 do i = k-1 włącznie zwiększając i o 1:
$\quad\quad$$\quad\quad$wynik <- gcd (wynik,m[i])
$\quad\quad$Zwróć wynik

Funkcja lcm(m[k],k):
$\quad\quad$wynik <- lcm(m[0],m[1])
$\quad\quad$Powtarzaj od i=2 do i = k-1 włącznie zwiększając i o 1:
$\quad\quad$$\quad\quad$wynik <- lcm(wynik,m[i])
$\quad\quad$Zwróć wynik

Funkcje korzystają z funkcji z zadania pierwszego. Korzystają one również z własności gcd(a,b,c) = gcd(gcd(a,b),c) oraz lcm(a,b,c) = lcm(lcm(a,b),c)

## 4
Algorytm:
Funkcja $gcd(a,b)$:
$\quad\quad$Jeżeli $b > a$ to zwróć $gcd (b,a)$
$\quad\quad$Jeżeli $b == 0$ to zwróć $a$
$\quad\quad$Jeżeli $a$%2==$0$ oraz $b$%2==$1$ to zwróć $gcd(\frac{a}{2},b)$
$\quad\quad$Jeżeli $a$%2==$1$ oraz $b$%2==$1$ to zwróć $gcd(a-b,b)$
$\quad\quad$Zwróć $2\times gcd(\frac{a}{2},\frac{b}{2})$

Algorytm rozpatrza 4 przypadki (dla a,b parzystych/nieparzystych) i zwraca odpowiednią wartość. Możemy zauważyć, że ten algorytm działa podobnie jak algorytm Euklidesa (z wyjątkiem dzielenia przez 2), lecz jest trochę szybszy.

**Co powinien zrobić algorytm, gdy na początku a i b są parzyste?**
Zwrócić $2\times gcd(\frac{a}{2},\frac{b}{2})$

**Jaka jest złożoność tego algorytmu?**

Za każdym razem otrzymamy albo dzielenie na 2 albo odejmowanie, które doprowadzi do dzielenia przez 2 (nieparzysta - nieparzysta = parzysta), czyli algorytm działa w czasie $O(log_2a + log_2b)$, gdzie a i b są naszymi danymi na wejściu.

## 8

### a)
**Jeśli $2^n-1$ jest liczbą pierwszą, to n jest liczbą pierwszą.**

Dowód:

Załóżmy, że $2^n-1$ jest liczbą pierwszą.
Załóżmy nie wprost, że $n = a\times b$, gdzie $a,b\in\mathbb{N}$ oraz $a\neq1$ i $b\neq1$

rozpiszmy $2^n-1$ według wzoru na $a^n-b^n$
$2^n-1=2^{a\times b} - 1 = (2^a)^b - 1 = (2^a-1)\times(\displaystyle\sum (2^a)^i\times 1^{n-i-1})$
Wiedząc, że $(2^a-1)\times(\displaystyle\sum (2^a)^i\times 1^{n-i-1})$ jest liczbą pierwszą wynika, że
$2^a-1$ jest równe $1$ lub $2^n-1$
$1^{\circ}$ $2^a-1 = 1$
Wtedy a = 1. Sprzeczność, bo w założeniu $a\neq 1$

$2^{\circ}$ $2^a-1 = 2^n-1$
Wtedy a = n. Sprzeczność, bo w założeniu $a\times b = n$ Czyli dla $a=n$, $b=1$.

Co kończy dowód, gdyż doszliśmy we wszystkich przypadkach do sprzeczności.

### b)
**Jeśli $a^n-1$ jest liczbą pierwszą, to a=2.**
Dowód:

Załóżmy, że $2^n-1$ jest liczbą pierwszą.
Rozpiszmy $a^n-1$ według wzoru na $a^n-b^n$

$a^n-1 = (a-1)\times(\displaystyle\sum a^i\times 1^{n-i-1})$
Wiedząc, że $(a-1)\times(\displaystyle\sum a^i\times 1^{n-i-1})$ jest liczbą pierwszą wynika, że $a-1$ jest równe 1 lub $a^n-1$

$1^{\circ}$ $a-1 = 1$
Wtedy a=2
$2^{\circ}$ $a-1 = a^n-1$
$a=a^n$
$a^n-a=0$
$a\times(a^{n-1} - 1) = 0$

Czyli $a=0$ lub $a = 1$ (dla tych wartości a, liczba $a^n-1$ jest albo równa 0 albo równa -1, co nie jest liczbą pierwszą z założenia.)

Czyli a = 2.

Co kończy dowód.

### c)

**Jeśli $2^n+1$ jest liczbą pierwszą, to n jest potęgą liczby 2.**

Dowód:

Załóżmy, że $2^n+1$ jest liczbą pierwszą.
Załóżmy nie wprost, że n nie jest potęgą liczby 2, czyli $n = 2^a\times b$, gdzie $a,b\in\mathbb{N}$ oraz $b\neq2^c$ gdzie $c\in\mathbb{N}\cup{0}$

Wtedy
$2^n+1 = 2^{2^a\times b}-(-1) = (2^{2^a})^b-(-1) = (2^{2^a}+1)\times(\displaystyle\sum (2^{2^a})^i\times (-1)^{n-i-1})$

Wiedząc, że $(2^{2^a}+1)\times(\displaystyle\sum (2^{2^a})^i\times (-1)^{n-i-1})$ jest liczbą pierwszą wynika, że $2^{2^a}+1 = 1$ lub $2^{2^a}+1 = 2^n+1$

$1^{\circ}$ $2^{2^a}+1 = 1$
Wtedy $2^{2^a} = 0$ Sprzeczność.

$2^{\circ}$ $2^{2^a}+1 = 2^n+1$
Wtedy $n=2^a$ Sprzeczność. Z założenia n nie jest potęgą liczby 2.

Co kończy dowód, gdyż doszliśmy we wszystkich przypadkach do sprzeczności.

## 12

$n_i$|$a_i$|$\quad\quad\quad$$m_i$$\quad\quad\quad$|$m_i^{-1}mod$ $n_i$|
27|11|$\frac{27\times64\times25}{27} = 1600$|$1600^{-1}mod$ $27 = 7 ^{-1}mod$ $27 = 4$|
64|12|$\frac{27\times64\times25}{64} = 675$|$675^{-1}mod$ $64 = 35 ^{-1}mod$ $64 = 11$|
25|13|$\frac{27\times64\times25}{25} = 1728$|$1728^{-1}mod$ $25 = 3 ^{-1}mod$ $25 = 17$|
$x = (\displaystyle\sum^3_{i=1}a_i\times m_i \times m_i^{-1}mod\space n_i)mod\space(27\times64\times25) =$
$=(11\times1600\times4 + 12\times675\times11+13\times1728\times17)mod\space43200 =$
$= (70400+89100+381888)mod\space43200 =541388\space mod\space43200 = 22988$

## 13
Znajdźmy takie $n_1,n_2,n_3,n_4,n_5$, że
$2^{n_1}\equiv1\space mod\space a_1$ dla $n_1 = 4$
$2^{n_2}\equiv1\space mod\space a_2$ dla $n_2 = 3$
$2^{n_3}\equiv1\space mod\space a_3$ dla $n_3 = 6$
$2^{n_4}\equiv1\space mod\space a_4$ dla $n_4 = 10$
$2^{n_5}\equiv1\space mod\space a_5$ dla $n_5 = 178$
gdzie $a_1=5,a_2=7,a_3=9,a_4=11,a_5=179$

Z własności modulo
$2^n\equiv1\space mod\space5\times7\times9\times11\times178 \implies n = lcm(n_1,n_2,n_3,n_4,n_5) + k\times5\times7\times9\times11\times178$ (gdzie $n_i$ spełnia $2^{n_i}\equiv1\space mod\space a_i, k \in\mathbb{N} \cup{0})$
Wtedy najmniejsze takie n jest dla k=0 i wynosi
$n = lcm(4,3,6,10,178) = 5340$

## 14
### a)
**Istnieje nieskończenie wiele liczb pierwszych w postaci 3k + 2**
Dowód przeprowadzę nie wprost.
Załóżmy, że istnieje skończenie wiele liczb pierwszych w postaci 3k + 2 i zapiszmy je jako $p_1,p_2,...,p_n$
Zauważmy, że jeśli liczba $x = 3k_1+2$ to wtedy $x^2 = 3k_2+1$, bo $(3k_1+2)^2 = 9k_1^2 + 12k_1 + 4 = 3(3k_1^2+4k_1+1) + 1 = 3k_2 + 1$.

Wtedy weżmy taką liczbę $s$, że $s = p_1^2\times p_2^2\times...\times p_n^2$, gdzie $p_i$ to kolejna liczba pierwsza postaci 3k+2 (jest to iloczyn wszystkich kwadratów liczb pierwszych postaci $3k+2$ ($p_i^2$ jest postaci $3k+1$)) i zauważmy, że s jest postaci $3k_3+1$ (Wynika to z wymnażania kolejnych nawiasów. Zawsze dostaniemy przy współczynnikach liczby podzielne przez 3, a ostatnia liczba po wymnożeniu tych nawiasów będzie równa 1, gdyż $1^n = 1$). Weźmy wtedy liczbę $z = s+1$, czyli liczba $z$ jest postaci $3k_3 + 2$. Wtedy rozpatrzmy 4 przypadki.

$1^\circ$ Liczba $z$ jest pierwsza.
Wtedy sprzeczność, ponieważ istnieje liczba pierwsza ($z$), która jest większa niż każda z wziętego na początku zadania zbioru.

$2^\circ$ Liczba $z$ ma dzielnik postaci 3q.
Wtedy sprzeczność, ponieważ liczba $z$ nie jest postaci 3q tylko 3q+2.

$3^\circ$ Liczba $z$ ma dzielnik postaci 3q + 1.
Wtedy sprzeczność, ponieważ liczba $z$ nie jest postaci 3q+1 tylko 3q+2.

$4^\circ$Liczba $z$ ma dzielnik postaci 3q + 2.
Jeżeli (3q+2) | z to wtedy możemy zauważyć, że (3q+2) | s (bo s to iloczyn kwadratów wszystkich liczb pierwszych postaci 3k+2). Skoro tak, to wtedy (3q+2) | 1 (bo z = s + 1) co daje wyraźną sprzeczność.

Wszystkie przypadki doprowadziłem do sprzeczności co kończy dowód.
### b)
**Istnieje nieskończenie wiele liczb pierwszych w postaci 4k + 3**
Dowód przeprowadzę nie wprost.
Załóżmy, że istnieje skończenie wiele liczb pierwszych w postaci 4k + 3 i zapiszmy je jako $p_1,p_2,...,p_n$
Zauważmy, że jeśli liczba $x = 4k_1 + 3$ to wtedy $x^2 = 4k_2+1$, bo $(4k + 3)^2 = 16k_1^2 + 24k_1 + 9 = 4(4k_1^2+6k_1+2) + 1 = 4k_2 + 1$.

Wtedy weżmy taką liczbę $s$, że $s = p_1^2\times p_2^2\times...\times p_n^2$, gdzie $p_i$ to kolejna liczba pierwsza postaci 4k+3 (jest to iloczyn wszystkich kwadratów liczb pierwszych postaci $4k+3$ ($p_i^2$ jest postaci $4k+1$)) i zauważmy, że s jest postaci $4k_3+1$ (Wynika to z wymnażania kolejnych nawiasów. Zawsze dostaniemy przy współczynnikach liczby podzielne przez 4, a ostatnia liczba po wymnożeniu tych nawiasów będzie równa 1, gdyż $1^n = 1$). Weźmy wtedy liczbę $z = s+2$, czyli liczba $z$ jest postaci $4k_3 + 3$. Wtedy rozpatrzmy 5 przypadków.

$1^\circ$ Liczba $z$ jest pierwsza.
Wtedy sprzeczność, ponieważ istnieje liczba pierwsza ($z$), która jest większa niż każda z wziętego na początku zadania zbioru.

$2^\circ$ Liczba $z$ ma dzielnik postaci 4q.
Wtedy sprzeczność, ponieważ liczba $z$ nie jest postaci 4q tylko 4q+1.

$3^\circ$ Liczba $z$ ma dzielnik postaci 4q + 1.
Wtedy sprzeczność, ponieważ liczba $z$ nie jest postaci 4q+1 tylko 4q+3.

$4^\circ$ Liczba $z$ ma dzielnik postaci 4q + 2.
Wtedy sprzeczność, ponieważ liczba $z$ nie jest postaci 4q+2 tylko 4q+3.

$5^\circ$Liczba $z$ ma dzielnik postaci 4q + 3.
Jeżeli (4q+3) | z to wtedy możemy zauważyć, że (4q+3) | s (bo s to iloczyn kwadratów wszystkich liczb pierwszych postaci 4k+3). Skoro tak, to wtedy (4q+3) | 2 (bo z = s + 2) co daje wyraźną sprzeczność.

Wszystkie przypadki doprowadziłem do sprzeczności co kończy dowód.