Matematyka dyskretna 1/Ćwiczenia 11: Teoria liczb II

Teoria liczb II

Ćwiczenie 1

Podaj zbiór rozwiązań następujących równań:

• $\displaystyle 21x\equiv _{36}5$,
• $\displaystyle 4x\equiv _{7}6$,
• $\displaystyle 3x\equiv _{33}27$,
• $\displaystyle 3x\equiv _{100}59$,
• $\displaystyle 2x\equiv _{4}3$,
• $\displaystyle 16x\equiv _{24}8$.

Rozwiązanie

• Równanie $\displaystyle 21x\equiv _{36}5$:
  • NWD $\displaystyle (21,36)=3$ ale $\displaystyle 3\not |5$, czyli równanie nie ma rozwiązań.
• Równanie $\displaystyle 4x\equiv _{7}6$:
  • NWD $\displaystyle (4,7)=1$, czyli równanie ma nieskończenie wiele rozwiązań,
  • $\displaystyle 1=2\cdot 4-7$, czyli zbiór rozwiązań to $\displaystyle \left\lbrace 2\cdot 6+7k;k\in \mathbb {Z} \right\rbrace =\left\lbrace 5+7k:k\in \mathbb {Z} \right\rbrace$.
• Równanie $\displaystyle 3x\equiv _{33}27$:
  • NWD $\displaystyle (3,33)=3$ oraz $\displaystyle 3|27$ czyli równanie ma nieskończenie wiele rozwiązań,
  • $\displaystyle 3=1\cdot 3+0\cdot 33$, czyli zbiór rozwiązań to $\displaystyle \left\lbrace 1\cdot {\frac {27}{3}}+{\frac {33}{3}}k:k\in \mathbb {Z} \right\rbrace =\left\lbrace 9+11k:k\in \mathbb {Z} \right\rbrace$.
• Równanie $\displaystyle 3x\equiv _{100}59$:
  • NWD $\displaystyle (3,100)=1$, czyli równanie ma nieskończenie wiele rozwiązań,
  • $\displaystyle 1=-33\cdot 3+100$, czyli zbiór rozwiązań to $\displaystyle \left\lbrace -33\cdot 59+100k:k\in \mathbb {Z} \right\rbrace =\left\lbrace 53+100k:k\in \mathbb {Z} \right\rbrace$.
• Równanie $\displaystyle 2x\equiv _{4}3$:
  • NWD $\displaystyle (2,4)=2$ ale $\displaystyle 2\not |3$, czyli równanie nie ma rozwiązań.
• Równanie $\displaystyle 16x\equiv _{24}8$:
  • NWD $\displaystyle (16,24)=8$ oraz $\displaystyle 8|8$, czyli równanie ma nieskończenie wiele rozwiązań,
  • $\displaystyle 8=-1\cdot 16+24$, czyli zbiór rozwiązań to $\displaystyle \left\lbrace -1\cdot {\frac {8}{8}}+{\frac {24}{8}}k:k\in \mathbb {Z} \right\rbrace =\left\lbrace 2+3k:k\in \mathbb {Z} \right\rbrace$.

Ćwiczenie 2

Wyznacz najmniejsze, nieujemne rozwiązania układu równań:

$\displaystyle {\begin{aligned}x&\equiv _{3}&2,\\x&\equiv _{5}&3,\\x&\equiv _{11}&4,\\x&\equiv _{16}&5.\end{aligned}}$

Rozwiązanie

NWD $\displaystyle (3,5)=$ NWD $\displaystyle (3,11)=$ NWD $\displaystyle (3,16)=$ NWD $\displaystyle (5,11)=$ NWD $\displaystyle (5,16)=$ NWD $\displaystyle (11,16)=1$, czyli możemy użyć Chińskiego Twierdzenia o Resztach:

• $\displaystyle N=3\cdot 5\cdot 11\cdot 16=2640$,
• $\displaystyle N_{1}={\frac {2640}{3}}=880$,
• $\displaystyle N_{2}={\frac {2640}{5}}=528$,
• $\displaystyle N_{3}={\frac {2640}{11}}=240$,
• $\displaystyle N_{4}={\frac {2640}{16}}=165$.

Zgodnie z procedurą czterokrotnie używamy rozszerzonego algorytmu Euklidesa otrzymując $\displaystyle x_{1},x_{2},x_{3},x_{4}$:

• NWD $\displaystyle (3,880)=1=-293\cdot 3+1\cdot 880$, $\displaystyle x_{1}=1$,
• NWD $\displaystyle (5,528)=1=-211\cdot 5+2\cdot 528$, $\displaystyle x_{2}=2$,
• NWD $\displaystyle (11,240)=1=-109\cdot 11+5\cdot 240$, $\displaystyle x_{3}=5$,
• NWD $\displaystyle (16,165)=1=31\cdot 16-3\cdot 165$, $\displaystyle x_{4}=-3$.

Pozostaje policzyć $\displaystyle x$:

$\displaystyle {\begin{aligned}x&=2\cdot 1\cdot 880+3\cdot 2\cdot 528+4\cdot 5\cdot 240+5\cdot (-3)\cdot 165\\&=1760+3168+4800-2475\\&=7253\equiv _{2640}1973.\end{aligned}}$

A więc $\displaystyle 1973$ jest najmniejszym, nieujemnym rozwiązaniem naszego układu równań.

Ćwiczenie 3

Wyznacz najmniejsze, nieujemne rozwiązania układu równań:

$\displaystyle {\begin{aligned}x&\equiv _{31}&23,\\x&\equiv _{12}&7,\\x&\equiv _{35}&12.\end{aligned}}$

Rozwiązanie

NWD $\displaystyle (31,12)=$ NWD $\displaystyle (31,35)=$ NWD $\displaystyle (12,35)=1$, czyli możemy użyć Chińskiego Twierdzenia o Resztach:

• $\displaystyle N=31\cdot 12\cdot 35=13020$,
• $\displaystyle N_{1}={\frac {13020}{31}}=420$,
• $\displaystyle N_{2}={\frac {13020}{12}}=1085$,
• $\displaystyle N_{3}={\frac {13020}{35}}=372$.

Zgodnie z procedurą trzykrotnie używamy rozszerzonego algorytmu Euklidesa otrzymując $\displaystyle x_{1},x_{2},x_{3}$:

• NWD $\displaystyle (31,420)=1=-149\cdot 31+11\cdot 420$, $\displaystyle x_{1}=11$,
• NWD $\displaystyle (12,1085)=1=-452\cdot 12+5\cdot 1085$, $\displaystyle x_{2}=5$,
• NWD $\displaystyle (35,372)=1=-85\cdot 35+8\cdot 372$, $\displaystyle x_{3}=8$.

Pozostaje policzyć $\displaystyle x$:

$\displaystyle {\begin{aligned}x&=23\cdot 11\cdot 420+7\cdot 5\cdot 1085+12\cdot 8\cdot 372\\&=106260+37975+35712\\&=179947\equiv _{13020}10687.\\\end{aligned}}$

A więc $\displaystyle 10687$ jest najmniejszym, nieujemnym rozwiązaniem naszego układu równań.

Ćwiczenie 4

Policz wartości funkcji Eulera:

• $\displaystyle \varphi (10)$,
• $\displaystyle \varphi (100)$,
• $\displaystyle \varphi (1000)$.

Rozwiązanie

• $\displaystyle \varphi (10)=\varphi (2)\varphi (5)=1\cdot 4=4$,
• $\displaystyle \varphi (100)=\varphi (2^{2})\varphi (5^{2})=(2^{2}-2)(5^{2}-5)=40$,
• $\displaystyle \varphi (1000)=\varphi (2^{3})\varphi (5^{3})=(2^{3}-2^{2})(5^{3}-5^{2})=400$.

Ćwiczenie 5

Policz możliwie szybko:

• $\displaystyle 16^{75}$ { mod} $\displaystyle 35$,
• $\displaystyle 2^{100}$ { mod} $\displaystyle 3$,
• $\displaystyle 21^{55}$ { mod} $\displaystyle 32$.

Rozwiązanie

• $\displaystyle 16^{75}$ { mod} $\displaystyle 35$:
  • $\displaystyle 16\perp 35$, czyli możemy skorzystać z Twierdzenia Eulera,
  • $\displaystyle \varphi (35)=\varphi (5)\cdot \varphi (7)=4\cdot 6=24$,
  • $\displaystyle 75$ { mod} $\displaystyle 24=3$,
  • $\displaystyle 3=(11)_{2}$,
  • liczymy wybrane potęgi $\displaystyle 16$ modulo $\displaystyle 35$:
    • $\displaystyle 16^{2}=256\equiv _{35}11$,
  • $\displaystyle 16^{75}\equiv _{35}16^{75}$ { mod} $\displaystyle 24=16^{3}=16^{2}\cdot 16^{1}\equiv _{35}11\cdot 16=176\equiv _{35}1$.
• $\displaystyle 2^{100}$ { mod} $\displaystyle 3$:
  • $\displaystyle 2\perp 3$, czyli możemy skorzystać z Twierdzenia Eulera,
  • $\displaystyle \varphi (3)=2$,
  • $\displaystyle 100$ { mod} $\displaystyle 2=0$,
  • $\displaystyle 2^{100}\equiv _{3}2^{100}$ { mod} $\displaystyle 2=2^{0}=1$.
• $\displaystyle 21^{55}$ { mod} $\displaystyle 32$:
  • $\displaystyle 21\perp 32$, czyli możemy skorzystać z Twierdzenia Eulera,
  • $\displaystyle \varphi (32)=\varphi (2^{5})=2^{5}-2^{4}=16$,
  • $\displaystyle 55$ { mod} $\displaystyle 16=7$,
  • $\displaystyle 7=(111)_{2}$,
  • liczymy wybrane potęgi $\displaystyle 21$ modulo $\displaystyle 32$:
    • $\displaystyle 21^{2}=441\equiv _{32}25$,
    • $\displaystyle 21^{4}\equiv _{32}25\cdot 25\equiv _{32}17$,
  • $\displaystyle 21^{55}\equiv _{32}16^{21}$ { mod} $\displaystyle 55=21^{7}=21^{4}\cdot 21^{2}\cdot 21^{1}\equiv _{32}17\cdot 25\cdot 21=8925\equiv _{32}29$.

Ćwiczenie 6

Funkcja $\displaystyle f$ liczbowa określona na zbiorze $\displaystyle \mathbb {N}$ jest multyplikatywna, jeśli dla dowolnych względnie pierwszych $\displaystyle m,n\in \mathbb {N}$ zachodzi

$\displaystyle f(mn)=f(m)f(n).$

Widzieliśmy, że $\displaystyle \varphi$-Eulera jest multyplikatywna. Pokaż, że:

1. funkcja $\displaystyle \mu$ Mobiusa jest multyplikatywna,
2. jeśli funkcja $\displaystyle f(n)=\sum _{d|n}g(d)$ jest multyplikatywna to $\displaystyle g(n)$ też.

Rozwiązanie

Rozważmy rozkłady dwu liczb naturalnych $\displaystyle m,n\in \mathbb {N}$ i ich rozkłady $\displaystyle m=p_{1}^{\alpha _{1}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}$, $\displaystyle n=q_{1}^{\beta _{1}}\cdot \ldots \cdot q_{l}^{\beta _{l}}$. Jeśli choć jedno $\displaystyle \alpha _{i}>1$ bądź $\displaystyle \beta _{i}>1$, to $\displaystyle \mu (m)=0$ lub $\displaystyle \mu (n)=0$, ale także $\displaystyle \mu (mn)=0$. Jeśli zaś liczby w rozkładach $\displaystyle m$ i $\displaystyle n$ się nie powtarzają, to względna pierwszość $\displaystyle m$ i $\displaystyle n$ gwarantuje, że nie powtarzają się także w rozkładzie iloczynu: $\displaystyle mn=p_{1}\cdot \ldots \cdot p_{k}q_{1}\cdot \ldots \cdot q_{l}$. Mamy więc:

$\displaystyle \mu (mn)=(-1)^{k+l}=(-1)^{k}(-1)^{l}=\mu (m)\mu (n),$

co dowodzi punktu 1.

Dla dowodu punktu 2, zauważmy najpierw, że jeśli $\displaystyle m\perp n$, to $\displaystyle \left\lbrace d:d|mn\right\rbrace =\left\lbrace d_{0}d_{1}:d_{0}|m,d_{1}|n\right\rbrace$. Korzystając ze wzoru inwersyjnego Mobiusa, udowodnionej powyżej multyplikatywności $\displaystyle \mu$ i założonej multyplikatywności $\displaystyle f$ mamy:

$\displaystyle {\begin{aligned}g(mn)&=\sum _{d|mn}\mu (d)f\left({\frac {mn}{d}}\right)=\sum _{d_{0}|m,d_{1}|n}\mu (d_{0}d_{1})f\left({\frac {mn}{d_{0}d_{1}}}\right)\\&=\sum _{d_{0}|m}\mu (d_{0})f\left({\frac {m}{d_{0}}}\right)\sum _{d_{1}|n}\mu (d_{1})f\left({\frac {n}{d_{1}}}\right)\\&=g(m)g(n).\end{aligned}}$

Ćwiczenie 7

Udowodnij, że liczba naturalna $\displaystyle n>1$ jest pierwsza wtedy i tylko wtedy, gdy $\displaystyle (n-1)!\equiv _{n}-1$.

Komentarz: Fakt ten znany jest jako Twierdzenie Wilsona. Pierwszy te prawidłowość zauważył John Wilson, student Edwarda Waringa. Żaden z nich nie był w stanie tego udowodnić. Pierwszy dowód przedstawił Lagrange w 1773 roku. Twierdzenie to daje potencjalną możliwość sprawdzenia czy liczba naturalna jest pierwsza. Nie znamy jednak efektywnych algorytmów obliczania silni, nawet w arytmetyce modularnej.

Wskazówka

Zauważ, że jeśli $\displaystyle n$ jest liczbą pierwszą, to dla $\displaystyle a\in \left\lbrace 1,\ldots ,n-1\right\rbrace$ istnieje $\displaystyle a'\in \left\lbrace 1,\ldots ,n-1\right\rbrace$ takie, że $\displaystyle aa'\equiv _{n}1$.

Rozwiązanie

Załóżmy najpierw, że $\displaystyle n$ jest złożona, czyli $\displaystyle n=ab$ dla $\displaystyle 1<a\leqslant b<n$. Wtedy $\displaystyle n|1\cdot 2\cdot \ldots \cdot a\cdot \ldots \cdot b\cdot \ldots \cdot (n-1)=(n-1)!$, czyli $\displaystyle (n-1)!\equiv _{n}0\not \equiv _{n}1$.

Załóżmy zatem, że liczba $\displaystyle n$ jest pierwsza. Zauważmy, że dla dowolnego $\displaystyle a\in \left\lbrace 1,\ldots ,n-1\right\rbrace$:

• jeśli $\displaystyle a^{2}\equiv _{n}1$, to $\displaystyle a=1$ lub $\displaystyle a=n-1$.

Rzeczywiście, $\displaystyle a^{2}\equiv _{n}1$ implikuje $\displaystyle (a-1)(a+1)=a^{2}-1=qn$ dla pewnego $\displaystyle q$. Z pierwszości $\displaystyle n$ mamy więc $\displaystyle n|(a-1)$ lub $\displaystyle n|(a+1)$, czyli $\displaystyle a\equiv _{n}1$ lub $\displaystyle a\equiv _{n}n-1$. Ponieważ $\displaystyle 1\leq a\leq n-1$, to przystawania te są po prostu równościami.

• istnieje dokładnie jedno $\displaystyle a'\in \left\lbrace 1,\ldots ,n-1\right\rbrace$ takie, że $\displaystyle aa'\equiv _{n}1$.

Istnienie gwarantuje rozszerzony algorytm Euklidesa. Istotnie, NWD $\displaystyle (a,n)=1$ daje $\displaystyle x,y$ takie, że $\displaystyle xa+yn=1$, czyli dla $\displaystyle a'=x$ { mod} $\displaystyle n$ mamy $\displaystyle a'a\equiv _{n}1$.

Dla dowodu jednoznaczności załóżmy, że $\displaystyle aa''\equiv _{n}1$. Wobec NWD $\displaystyle (a,n)=1$, prawo skracania daje jednak $\displaystyle a'\equiv _{n}a''$, czyli $\displaystyle a'=a''$.

Te dwie uwagi dają, że w iloczynie

$\displaystyle (n-1)!=1\cdot 2\cdot \ldots \cdot (n-1)$

każdy czynnik $\displaystyle a\neq 1,n-1$ ma czynnik $\displaystyle a'\neq a$ do siebie odwrotny, tzn. taki, że $\displaystyle aa'\equiv _{n}1$. A zatem

$\displaystyle (n-1)!\equiv _{n}1\cdot (n-1)\equiv _{n}-1.$