Lukujärjestelmät
Kymmenjärjestelmä
Määrkymmenjä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 onjaollinen/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äärsuurin 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\) onalkuluku/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.
LauseEukleideen 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

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äärLineaarinen 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 \).
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.