Lukujärjestelmät

Kymmenjärjestelmä

Määr kymmenjärjestelmä / decimal system esim. \( 1907 = 1\cdot 10^3+9\cdot 10^2+0\cdot 10^1 + 7\cdot 10^0\).

Muitajärjestelmiä

Esim Kahdeksanjärjestelmä
▻▻ Kahdeksanjärjestelmä \(103 = 12\cdot 8 +7 = (1\cdot 8 +4)\cdot 8 + 7 = 147_8\).
▻▻ \(2007_8 = 2\cdot 8^3 + 0\cdot 8^2+ 0\cdot 8^1+ 7 \cdot 8^0 = 1031\).

Lause Jakoyhtälö / Euclidean division \(a=qb+r,\ \ 0\leq r \lt |b|\).

Yksikäsitteisyyslause

Lause Olkoot \(n,k\in \mathbb{N} \). Tällöin on yksikäsitteiset kokonaisuluvut \(s,a_0,a_1,\dots,a_s\), joille:
(1) \(n=a_s k^s +a _{s-1} k ^{s-1} +\cdot +a_1k + a_0\).;
(2) \( 0\leq a_i \lt k,\ \forall i=0,1,\dots,s\);
(3) \(a_s\gt0\).

Alukulukuteoria

Jaollisuus

Määr Lukun n on jaollinen/divisible luvulla m, jos \(n=km,\ k\in \mathbb{Z} \).
▻▻ merkitään \(m|n\).

Lause Olkoot \(n,m,d,a,b \in \mathbb{Z} \). Tällöin,
(1) \(n|n\) refleksiivisyys ;
(2) \( \begin{Bmatrix} d|n\\ n|m \end{Bmatrix} ⇒ d|m \) transitiivisuus ;
(3) \( \begin{Bmatrix} d|n\\ n|m \end{Bmatrix} ⇒ d|(an+bm) \) lineaarisuus ;
(4) \(d|n ⇒ ad|an\) ;
(5) \(ad|an ⇒ d|n\) ;
(6) \(1|n\) ;
(7) \(n|0\) ;
(8) \(0|n ⇒ n=0\) ;
(9) \(d|n ⇒ |d|\leq|n|\) vertailu;
(10) \( \begin{Bmatrix} d|n \\ n|d \end{Bmatrix} ⇒ |d|=|n|\) .

Suurin yhteinen tekijä

Määr suurin yhteinen tekijä / maximal common divisor \(\text{syt}(a,b)=\max\{d\in \mathbb{N} : d|a \text{ ja } d|b\}\).

Lemma \(a=qb+r\ ⇒ \ \text{syt}(a,b)=\text{syt}(b,r)\).

algoritmi Eukleideen algoritmi/Euclidean algorithm \(r _{n-1} =\text{syt}(a,b)\).
▻▻ \(\begin{cases} a=q_1 b +r_1 &0\leq r_1\lt b \\ b=q_2 r_1 +r_2 &0\leq r_2\lt r_1 \\ r_1 = q_3 r_2 + r_3 &0\leq r_3\lt r_2 \\ \vdots \\ r _{n-3} =q _{n-1} r _{n-2} + r _{n-2} &0\leq r _{n-1} \lt r _{n-2} \\ r _{n-2} = q_n r _{n-1} +r_n &r_n=0 \end{cases} \).
▻▻ ▻▻ koska \(\text{syt}(a,b)=\text{syt}(b,r_1)=\text{syt}(r_1,r_2)=\cdots = \text{syt} (r _{n-2} ,r _{n-1} )\).

Lause Bezoutin yhtälö/Bezout equation \(\exists x,y\in \mathbb{Z} :\ \text{syt}(a,b)=xa+yb\).

Seuraus \(\begin{Bmatrix} c|a \\ c|b \end{Bmatrix} \ ⇔ \ c| \text{syt}(a,b)\).

Lause \(c=ka+lb \ ⇔ \ \text{syt}(a,b) | c \).

Määr a ja b ovat suhteellisia alkulukuja/relatively prime jos \(\text{syt}(a,b)=1 \), ja että a,b ovat keskenään jaottomia/coprime.

Seuraus Olkoot \(a,b\in \mathbb{Z} \) keskenään jaottomia. Tällöin
(1) \(\begin{Bmatrix} a|c \\ b|c \end{Bmatrix} ⇒ ab|c \);
(2) \(a|bc \ ⇒ \ a|c\).

Lukujen jako alkutekijöihin

Määr Luku \( p\gt 1\) on alkuluku/prime jos sen ainoat positiiviset tekijät ovat \(1,p\). Joka se ei ole alkuluku, sanotaan yhdistetyksi luvuksi/composite
▻▻ huom, luku 1 ei ole alkuluku eikä yhdistetty luku.

Lause Artmetiikan peruslause Jokainen luonnollinen luku \(n\geq 2\) voidaan esittää alkulukujen tulona.

Lemma Lunnollinen luku \(n\geq 2\) on alkuluku tai alkulukujen tulo.

Lemma Eukleideen lemma Alkuluku \(p|(ab) \ ⇒ \ p|a \text{ tai } p|b\).
▻▻ Yleisemmin, alkuluku \(p| (a_1\cdots a_n) ⇒ p|a_i\) jollain i.

Määr Luvun n alkulukutekijesitys/prime factor representation on \(n=p _{1}^{\epsilon_1} \cdots p _{k}^{\epsilon_k} \).

Lemma n on yhdistetty luku ⇔ \(\exists \text{ alkuluku/prime } p\leq\sqrt n:\ p|n\).

Seuraus Olkoot \( n,a\in \mathbb{N}.\ \ \sqrt[n]a \) on rationaaliluku ⇒ se on luonolllinen luku, erityisesti \(a=r^n \text{ jollain } r\in \mathbb{N} \).

Alkulukujen esiintymistiheydestä

Prime number: frequency of occurrence.

Lause Eukleideen lause Alkulukuja on äärettömän monta.

Lause Olkoot \(a,b\in \mathbb{Z},\ a\gt 0.\ \ \text{syt}(a,b)=0 \ ⇒ \text{muotoa } p=an+b \) olevia alkulukuja on äärettömän monta.

Seuraus \(p_n \leq 2 ^{2 ^{n-1} } \).

Lause Kaikille \(n\in \mathbb{N} ,n\geq 2\) on n-1 peräkkäistä/consective luonnollista lukua, joista mikään ei ole alkuluku.

Määr alkulukukaksonen/twin prime: \(p,p+2\) ovat alkulukuja. alkulukuserkukset/cousin primes: \(p,p+4\) ovat alkulukuja.

Lause \(p_n\) alkuluku ja \(k_n, k_n +2\) alkulukukaksospari. Tällöin
▻▻ \(\sum\limits_{n=1}^{ \infty} \frac{1}{p_n} =\infty \);
▻▻ \( \sum\limits_{n=1}^{ \infty} \frac{1}{k_n} + \frac{1}{k_n+2} \lt\infty\).

Lause Alkulukulause / Prime number theorem \( \lim\limits_{x \to \infty} \frac{\frac{ \pi(x)}{x } }{\frac{ 1}{ \log x} } = \lim\limits_{x \to \infty} \frac{\pi(x)}{x} \log x =1 \):
▻▻ Määritellään funktio \(\pi:[0,\infty)\to \mathbb{N} \cup \{0\}:\ \ \pi (x) = \#\{p: p \text{ on alkuluku } p\leq x\}\).

Esim Eratostheneen seula / Sieve of Eratosthenes

Lemma Fermat’n luvut \(F_n = 2 ^{2^n} +1.\ \ \ \text{syt}(F_n,F_m)=1,\ n\neq m \).

Lause \(a^n -1\) on alkuluku ⇒ \(a=2,\ n\) on alkuluku.

Esim Mersennen alkuluvut on muotoa \(2^p-1\).
▻▻ voi olla alkuluku vain jos p on alkuluku;
▻▻ on äärettömän monta (konjektuuri);
▻▻ mutta \(m _{11} = 2 ^{11} -1\) ei ole alkuluku;
▻▻ \(\text{syt}(M_n,M_k)=1,\ \ n\neq k \).

Määr Luku n on täydellinen/perfect jos se on tiseään aidosti pienempien positiivisten ekijöidensä summa.
▻▻ Positiiviset tekijät \( 1=m_1 \lt m_2 \lt \cdots \lt m_k \lt m _{k+1} =n \), ja sitten, että \(n= 1+ m_2 +\cdots + m_k\).

Lause Olkoon p alkuluku
(1) \(2^p-1\) alkuluku ⇒ \(n= 2 ^{p-1} (2^p -1)\) on täydellinen.
(2）Jos luku n on parillinen ja täydellinen, niin on Mersennen alkuluku \(2^p-1:\ n= 2 ^{p-1} (2^p-1)\).

Kokonaislukujen jaollisuus

Jakoyhtälö on yksikäsitteiset \(q,r\in \mathbb{Z}:\ \ a=qb+r,\ \ 0\leq r\lt |b|\).

Jaollisuus kymmenjärjestelmässä

Olkoon \(n=a_s 10^2 + \cdots + a_1 10 + a_0 := a_s \cdots a_1 a_0\).

Lause 1. 2. 3. ja 4. jaollisuuslause: luku n on jaollinen
(1.1) 2:lla ⇔ \(2|a_0 \);
(1.2) 5:lla ⇔ \(a_0\in\{0,5\}\);
(1.3) 10:lla ⇔ \(a_0=0\).
(2.1) 4:lla ⇔ \(4| a_1 a_0\).
(3.1) 50:lla ⇔ \(a_1 a_0\in\{00,50\}\);
(3.2) 25:lla ⇔ \(a_1 a_0\in\{00,25,50,75\}\).
(4.1) 8:lla ⇔ \( 8 | a_2 a_1 a_0\).
(5.1) 3:lla ⇔ \(3|\sum a_i\) (numerosumma);
(5.1) 9:lla ⇔ \(9|\sum a_i\) (numerosumma).
(6.1) 11:lla ⇔ \(11| \sum (-1)^i a_i\) (vuorottelevan numerosumma).

Kongruenssi

Kongruenssin määritelmä

Määr Luku a on kongruentti/congruent luvun b kanssa modulo n
▻▻ \(a \equiv b \ (\text{mod }n) \ ⇔ \ n|(a-b)\) .

Huom \(a \equiv b \ (\text{mod }n) \ ⇔ \):
(1) \(a-b=kn \ ⇔ \ a=b+kn\);
(2) \(\begin{cases} a=kn+r \\ b=ln+r \end{cases} \) (samat jakojännökset);
(3) \(a \equiv r \ (\text{mod }n) ,\ 0\leq r\lt n\), niin r on jakojännös;
(4) \(a \equiv 0 \ (\text{mod }n) \ ⇔ \ n|a\).

Lause Kongruenssi on \(\mathbb{Z} \):n ekvivalenssirelaatio. Siis:
(1) \(a \equiv a \ (\text{mod }n) \);
(2) \(a \equiv b \ (\text{mod }n) \ ⇒ \ b \equiv a \ (\text{mod }n) \);
(3) \(\begin{Bmatrix} a \equiv b \ (\text{mod }n) \\ b \equiv c \ (\text{mod }n) \end{Bmatrix} ⇒ \ a \equiv c \ (\text{mod }n) \).

Lause Lakusännöt
(1) \(\begin{Bmatrix} a \equiv b \ (\text{mod }n) \\ c \equiv d \ (\text{mod }n) \end{Bmatrix} ⇒ ax+cy \equiv bx+dy \ (\text{mod }n) \);
(2) \(\begin{Bmatrix} a \equiv b \ (\text{mod }n) \\ c \equiv d \ (\text{mod }n) \end{Bmatrix} ⇒ ac \equiv bd \ (\text{mod }n) \);
(3) \(a \equiv b \ (\text{mod }n) \ ⇒ \ a^m \equiv b^m \ (\text{mod }n) \).

Lause Supistussääntö / contraction rule: olkoon \(ac \equiv bc \ (\text{mod }n) \).
▻▻ Jos \( \text{syt}(n,c)=1 \ ⇒ \ a \equiv b \ (\text{mod }n) \);
▻▻ Yleisemmin, jos \(\text{syt}(n,c) =d \ ⇒ \ a \equiv b \ (\text{mod }\frac{n}{d} ) \).

Määr Kongruenssiluokka mudulo n: \([a]_n = \{b\in \mathbb{Z} : a \equiv b \ (\text{mod }n) \}\).

Lemma \(n\in \mathbb{N} ,\ a,b\in \mathbb{Z} \):
(1) \(a\in [a]_n\);
(2) \(a \equiv b \ (\text{mod }n) \ ⇔ \ [a]_n = [b]_n\);
(3) joko \([a]_n=[b]_n\) tai \([a]_n \cap [b]_n = \emptyset\).

Lause Olkoon n. Kongruenssiluokat \([0]_n, [1]_n,\dots,[n-1]_n\) ovat erillisiä ja niiden yhdiste on \(\mathbb{Z} \).

Määr Lakutoimitukset \(\mathbb{Z} _n\): ssä:
▻▻ \(\begin{cases} [a]_n \pm [b]_n = [a\pm b]_n \\ [a]_n [b]_n = [ab]_n \end{cases} \).

Esim Olkoon \( P(x)=c_0+c_1 x + c_2 x^2 + \cdots + c_k x^k,\ \ c_\cdot\in \mathbb{Z} \).
▻▻ Tällöin, \( a \equiv b \ ( \text{mod }n) \ ⇒ \ P(a) \equiv P(b) \ ( \text{mod }n) \).

Lineaarien kongruenssi

Määr Lineaarinen kongruenssiyhtälö \( ax \equiv b \ ( \text{mod }n) \).

Esim \( 2x \equiv 6 \ ( \text{mod }12) \):llä on ratkaisut \( x=3,\ x=9, \dots \) tai \( x=[3] _{12} \text{ tai } [9] _{12} \).

Huom Joko \( [c]_n \):n kaikki luvut ovat lineaarisen kongruenssiyhtälön kongruenssiyhtälön rakisuja tai mikään luvuista ei ole.
▻▻ yhtälöön ratkaisua haettaessa riittää kohdan \( 0,1,\dots, n-1 \).

Lause Lineaarisen kongruenssin lause Olkoon \( d= \text{syt}(a,n) \).
(1) \( \text{syt}(a,n) \not | b \ ⇒ \ ax \equiv b \ ( \text{mod }n) \):lla ei ole ratkaisua;
(2) \( \text{syt}(a,n) | b \ ⇒ \ ax \equiv b \ ( \text{mod }n) \):lla on \( \text{syt}(a,n) \). ratkaisua (kongruenssiluokkaa)

▻▻ haetaan \( ak_0+nl_0= \text{syt}(a,n) \). Tällöin, \( x_0 = \frac{b}{\text{syt}(a,n)} k_0 \) on yhtälön ratkaisu.
▻▻ kaikki rakaistu saadaan \( x \equiv x_0 + i \frac{ n}{ \text{syt}(a,n)} \ ( \text{mod }n),\ \ \ i=0,1,\dots, \text{syt}(a,n)-1 \).

Lause Kiinalainen jäännöslause
▻▻ Olkoot \( \text{syt}(n_i,n_j)=1 \) aina. Tällöin, kongruenssiyhtälöryhmällä \( \begin{cases} x \equiv b_1 \ ( \text{mod }n_1) \\ x \equiv b_2 \ ( \text{mod }n_2) \\ \dots \\ x \equiv b_k \ ( \text{mod }n_k) \end{cases} \) on yksikäsitteinen ratkaisu.