Matematyka dyskretna 1/Ćwiczenia 11: Teoria liczb II

Teoria liczb II

Ćwiczenie ex mod rownania

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 ex mod uklad1

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x&\equiv_3&2,\\ x&\equiv_5&3,\\ x&\equiv_{11}&4,\\ x&\equiv_{16}&5. \endaligned}

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$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x&=2\cdot1\cdot880+3\cdot2\cdot528+4\cdot5\cdot240+5\cdot(-3)\cdot165\\ &=1760+3168+4800-2475\\ &=7253\equiv_{2640}1973. \endaligned}

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

Ćwiczenie ex mod uklad2

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x&\equiv_{31}&23,\\ x&\equiv_{12}&7,\\ x&\equiv_{35}&12. \endaligned}

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$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x&=23\cdot11\cdot420+7\cdot5\cdot1085+12\cdot8\cdot372\\ &=106260+37975+35712\\ &=179947\equiv_{13020}10687.\\ \endaligned}

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

Ćwiczenie ex mod policz funkcje Eulera

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 ex

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$,
  • Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle 16^{75}\equiv_{35}16^{75 } { mod} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle 24}=16^3=16^2\cdot16^1\equiv_{35}11\cdot16=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$,
  • Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle 2^{100}\equiv_{3}2^{100 } { mod} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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$,
  • Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle 21^{55}\equiv_{32}16^{21 } { mod} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle 55}=21^7=21^4\cdot21^2\cdot21^1\equiv_{32}17\cdot25\cdot21=8925\equiv_{32}29} .

Ćwiczenie ex mod multyplikatywnosc mu

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:

funkcja $\displaystyle \mu$ Mobiusa jest multyplikatywna,

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned g(mn)&=\sum_{d|mn}\mu(d)f\left( \frac{mn}{d} \right)=\sum_{d_0|m,d_1|n}\mu(d_0d_1)f\left( \frac{mn}{d_0d_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). \endaligned}

Ćwiczenie ex mod twierdzenie Wilsona

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.$