Matematyka dyskretna 1/Ćwiczenia 11: Teoria liczb II

From Studia Informatyczne

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\cdot4-7, czyli zbiór rozwiązań to \displaystyle \left\lbrace 2\cdot6+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\cdot3+0\cdot33, 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\cdot3+100, czyli zbiór rozwiązań to \displaystyle \left\lbrace -33\cdot59+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\cdot16+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 \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\cdot5\cdot11\cdot16=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\cdot3+1\cdot880, \displaystyle x_1=1,
  • NWD \displaystyle  (5,528)=1=-211\cdot5+2\cdot528, \displaystyle x_2=2,
  • NWD \displaystyle  (11,240)=1=-109\cdot11+5\cdot240, \displaystyle x_3=5,
  • NWD \displaystyle  (16,165)=1=31\cdot16-3\cdot165, \displaystyle x_4=-3.

Pozostaje policzyć \displaystyle x:


\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 3

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


\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\cdot12\cdot35=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\cdot31+11\cdot420, \displaystyle x_1=11,
  • NWD \displaystyle  (12,1085)=1=-452\cdot12+5\cdot1085, \displaystyle x_2=5,
  • NWD \displaystyle  (35,372)=1=-85\cdot35+8\cdot372, \displaystyle x_3=8.

Pozostaje policzyć \displaystyle x:


\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 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\cdot4=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\perp35, czyli możemy skorzystać z Twierdzenia Eulera,
    • \displaystyle \varphi(35)=\varphi(5)\cdot\varphi(7)=4\cdot6=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\cdot16^1\equiv_{35}11\cdot16=176\equiv_{35}1.
  • \displaystyle 2^{100} { mod} \displaystyle   3:
    • \displaystyle 2\perp3, 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\perp32, 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\cdot25\equiv_{32}17,
    • \displaystyle 21^{55}\equiv_{32}16^{21 { mod} \displaystyle   55}=21^7=21^4\cdot21^2\cdot21^1\equiv_{32}17\cdot25\cdot21=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_kq_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_0d_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 \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 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\cdot2\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_n1, to \displaystyle a=1 lub \displaystyle a=n-1.

Rzeczywiście, \displaystyle a^2\equiv_n1 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_n1 lub \displaystyle a\equiv_nn-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_n1.

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

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_na'', czyli \displaystyle a'=a''.

Te dwie uwagi dają, że w iloczynie


\displaystyle (n-1)!=1\cdot2\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_n1\cdot(n-1)\equiv_n-1.