Matematyka dyskretna 1/Ćwiczenia 11: Teoria liczb II

Teoria liczb II

Ćwiczenie 1

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

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

Rozwiązanie

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

Ćwiczenie 2

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

$\begin{array}{rlr}x& {\equiv }_3& 2,\\ x& {\equiv }_5& 3,\\ x& {\equiv }_{11}& 4,\\ x& {\equiv }_{16}& 5\end{array}$

Rozwiązanie

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

• $N=3\cdot 5\cdot 11\cdot 16=2640$,
• $N_1=\frac{2640}{3}=880$,
• $N_2=\frac{2640}{5}=528$,
• $N_3=\frac{2640}{11}=240$,
• $N_4=\frac{2640}{16}=165$.

Zgodnie z procedurą czterokrotnie używamy rozszerzonego algorytmu Euklidesa otrzymując $x_1,x_2,x_3,x_4$:

• NWD $(3,880)=1=-293\cdot 3+1\cdot 880$, $x_1=1$,
• NWD $(5,528)=1=-211\cdot 5+2\cdot 528$, $x_2=2$,
• NWD $(11,240)=1=-109\cdot 11+5\cdot 240$, $x_3=5$,
• NWD $(16,165)=1=31\cdot 16-3\cdot 165$, $x_4=-3$.

Pozostaje policzyć $x$:

$\begin{array}{rl}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{array}$

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

Ćwiczenie 3

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

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

Rozwiązanie

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

• $N=31\cdot 12\cdot 35=13020$,
• $N_1=\frac{13020}{31}=420$,
• $N_2=\frac{13020}{12}=1085$,
• $N_3=\frac{13020}{35}=372$.

Zgodnie z procedurą trzykrotnie używamy rozszerzonego algorytmu Euklidesa otrzymując $x_1,x_2,x_3$:

• NWD $(31,420)=1=-149\cdot 31+11\cdot 420$, $x_1=11$,
• NWD $(12,1085)=1=-452\cdot 12+5\cdot 1085$, $x_2=5$,
• NWD $(35,372)=1=-85\cdot 35+8\cdot 372$, $x_3=8$.

Pozostaje policzyć $x$:

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

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

Ćwiczenie 4

Policz wartości funkcji Eulera:

• $\phi (10)$,
• $\phi (100)$,
• $\phi (1000)$.

Rozwiązanie

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

Ćwiczenie 5

Policz możliwie szybko:

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

Rozwiązanie

• $16^{75}$ { mod} $35$:
  • $16\perp 35$, czyli możemy skorzystać z Twierdzenia Eulera,
  • $\phi (35)=\phi (5)\cdot \phi (7)=4\cdot 6=24$,
  • $75${ mod}$24=3$,
  • $3=(11{)}_2$,
  • liczymy wybrane potęgi $16$ modulo $35$:
    • $16^2=256{\equiv }_{35}11$,
  • $16^{75}{\equiv }_{35}16^{75}${ mod}$24=16^3=16^2\cdot 16^1{\equiv }_{35}11\cdot 16=176{\equiv }_{35}1$.
• $2^{100}${ mod}$3$:
  • $2\perp 3$, czyli możemy skorzystać z Twierdzenia Eulera,
  • $\phi (3)=2$,
  • $100$ { mod} $2=0$,
  • $2^{100}{\equiv }_3{2}^{100}$ { mod} $2=2^0=1$.
• $21^{55}$ { mod} $32$:
  • $21\perp 32$, czyli możemy skorzystać z Twierdzenia Eulera,
  • $\phi (32)=\phi (2^5)=2^5-2^4=16$,
  • $55$ { mod} $16=7$,
  • $7=(111{)}_2$,
  • liczymy wybrane potęgi $21$ modulo $32$:
    • $21^2=441{\equiv }_{32}25$,
    • $21^4{\equiv }_{32}25\cdot 25{\equiv }_{32}17$,
  • $21^{55}{\equiv }_{32}16^{21}$ { mod} $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 $f$ liczbowa określona na zbiorze $\mathbb{\mathbb{N}}$ jest multyplikatywna, jeśli dla dowolnych względnie pierwszych $m,n\in \mathbb{\mathbb{N}}$ zachodzi

$f(mn)=f(m)f(n)$

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

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

Rozwiązanie

Rozważmy rozkłady dwu liczb naturalnych $m,n\in \mathbb{\mathbb{N}}$ i ich rozkłady $m=p_1^{{\alpha }_1}\cdot \dots \cdot p_k^{{\alpha }_k}$, $n=q_1^{{\beta }_1}\cdot \dots \cdot q_l^{{\beta }_l}$. Jeśli choć jedno ${\alpha }_i>1$ bądź ${\beta }_i>1$, to $\mu (m)=0$ lub $\mu (n)=0$, ale także $\mu (mn)=0$. Jeśli zaś liczby w rozkładach $m$ i $n$ się nie powtarzają, to względna pierwszość $m$ i $n$ gwarantuje, że nie powtarzają się także w rozkładzie iloczynu: $mn=p_1\cdot \dots \cdot p_k{q}_1\cdot \dots \cdot q_l$. Mamy więc:

$\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 $m\perp n$, to $\{d:d|mn\}=\{d_0{d}_1:d_0|m,d_1|n\}$. Korzystając ze wzoru inwersyjnego Mobiusa, udowodnionej powyżej multyplikatywności $\mu$ i założonej multyplikatywności $f$ mamy:

$\begin{array}{rl}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{array}$

Ćwiczenie 7

Udowodnij, że liczba naturalna $n>1$ jest pierwsza wtedy i tylko wtedy, gdy $(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 $n$ jest liczbą pierwszą, to dla $a\in \{1,\dots ,n-1\}$ istnieje $a^{\prime }\in \{1,\dots ,n-1\}$ takie, że $a{a}^{\prime }{\equiv }_{n}1$.

Rozwiązanie

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

Załóżmy zatem, że liczba $n$ jest pierwsza. Zauważmy, że dla dowolnego $a\in \{1,\dots ,n-1\}$:

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

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

• istnieje dokładnie jedno $a^{\prime }\in \{1,\dots ,n-1\}$ takie, że $a{a}^{\prime }{\equiv }_{n}1$.

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

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

Te dwie uwagi dają, że w iloczynie

$(n-1)!=1\cdot 2\cdot \dots \cdot (n-1)$

każdy czynnik $a\ne 1,n-1$ ma czynnik $a^{\prime }\ne a$ do siebie odwrotny, tzn. taki, że $a{a}^{\prime }{\equiv }_{n}1$. A zatem

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