Matematyka dyskretna 1/Ćwiczenia 11: Teoria liczb II: Różnice pomiędzy wersjami
m Zastępowanie tekstu – „,↵</math>” na „</math>,” |
m Zastępowanie tekstu – „<math> ” na „<math>” |
||
Linia 128: | Linia 128: | ||
{{cwiczenie|5|cw 5| | {{cwiczenie|5|cw 5| | ||
Policz możliwie szybko: | Policz możliwie szybko: | ||
* <math>16^{75}</math>{ mod}<math> 35</math>, | * <math>16^{75}</math>{ mod}<math>35</math>, | ||
* <math>2^{100}</math>{ mod}<math> 3</math>, | * <math>2^{100}</math>{ mod}<math>3</math>, | ||
* <math>21^{55}</math>{ mod}<math> 32</math>. | * <math>21^{55}</math>{ mod}<math>32</math>. | ||
}} | }} | ||
Linia 142: | Linia 142: | ||
** liczymy wybrane potęgi <math>16</math> modulo <math>35</math>: | ** liczymy wybrane potęgi <math>16</math> modulo <math>35</math>: | ||
*** <math>16^2=256\equiv_{35}11</math>, | *** <math>16^2=256\equiv_{35}11</math>, | ||
** <math>16^{75}\equiv_{35}16^{75}</math>{ mod}<math> 24=16^3=16^2\cdot 16^1 \equiv_{35}11\cdot16=176\equiv_{35}1</math>. | ** <math>16^{75}\equiv_{35}16^{75}</math>{ mod}<math>24=16^3=16^2\cdot 16^1 \equiv_{35}11\cdot16=176\equiv_{35}1</math>. | ||
* <math>2^{100}</math>{ mod}<math> 3</math>: | * <math>2^{100}</math>{ mod}<math>3</math>: | ||
** <math>2\perp3</math>, czyli możemy skorzystać z Twierdzenia Eulera, | ** <math>2\perp3</math>, czyli możemy skorzystać z Twierdzenia Eulera, | ||
** <math>\varphi(3)=2</math>, | ** <math>\varphi(3)=2</math>, | ||
** <math>100</math> { mod} <math> 2=0</math>, | ** <math>100</math> { mod} <math>2=0</math>, | ||
** <math>2^{100}\equiv_{3}2^{100}</math> { mod} <math> 2=2^0=1</math>. | ** <math>2^{100}\equiv_{3}2^{100}</math> { mod} <math>2=2^0=1</math>. | ||
* <math>21^{55}</math> { mod} <math> 32</math>: | * <math>21^{55}</math> { mod} <math>32</math>: | ||
** <math>21\perp32</math>, czyli możemy skorzystać z Twierdzenia Eulera, | ** <math>21\perp32</math>, czyli możemy skorzystać z Twierdzenia Eulera, | ||
** <math>\varphi(32)=\varphi(2^5)=2^5-2^4=16</math>, | ** <math>\varphi(32)=\varphi(2^5)=2^5-2^4=16</math>, | ||
** <math>55</math> { mod} <math> 16=7</math>, | ** <math>55</math> { mod} <math>16=7</math>, | ||
** <math>7=(111)_2</math>, | ** <math>7=(111)_2</math>, | ||
** liczymy wybrane potęgi <math>21</math> modulo <math>32</math>: | ** liczymy wybrane potęgi <math>21</math> modulo <math>32</math>: | ||
*** <math>21^2=441\equiv_{32}25</math>, | *** <math>21^2=441\equiv_{32}25</math>, | ||
*** <math>21^4\equiv_{32}25\cdot25\equiv_{32}17</math>, | *** <math>21^4\equiv_{32}25\cdot25\equiv_{32}17</math>, | ||
** <math>21^{55}\equiv_{32}16^{21}</math> { mod} <math> 55=21^7=21^4\cdot21^2\cdot21^1\equiv_{32}17\cdot25\cdot21=8925\equiv_{32}29</math>. | ** <math>21^{55}\equiv_{32}16^{21}</math> { mod} <math>55=21^7=21^4\cdot21^2\cdot21^1\equiv_{32}17\cdot25\cdot21=8925\equiv_{32}29</math>. | ||
</div></div> | </div></div> | ||
Linia 246: | Linia 246: | ||
Istnienie gwarantuje rozszerzony algorytm Euklidesa. | Istnienie gwarantuje rozszerzony algorytm Euklidesa. | ||
Istotnie, NWD <math>(a,n)=1</math> daje <math>x,y</math> takie, | Istotnie, NWD <math>(a,n)=1</math> daje <math>x,y</math> takie, | ||
że <math>xa+yn=1</math>, czyli dla <math>a'=x</math> { mod} <math> n</math> mamy <math>a'a\equiv_n1</math>. | że <math>xa+yn=1</math>, czyli dla <math>a'=x</math> { mod} <math>n</math> mamy <math>a'a\equiv_n1</math>. | ||
Dla dowodu jednoznaczności załóżmy, że <math>aa'' \equiv_n 1</math>. Wobec NWD <math>(a,n)=1</math>, prawo skracania daje jednak <math>a'\equiv_na''</math>, czyli <math>a'=a''</math>. | Dla dowodu jednoznaczności załóżmy, że <math>aa'' \equiv_n 1</math>. Wobec NWD <math>(a,n)=1</math>, prawo skracania daje jednak <math>a'\equiv_na''</math>, czyli <math>a'=a''</math>. |
Aktualna wersja na dzień 22:14, 11 wrz 2023
Teoria liczb II
Ćwiczenie 1
Podaj zbiór rozwiązań następujących równań:
- ,
- ,
- ,
- ,
- ,
- .
Ćwiczenie 2
Wyznacz najmniejsze, nieujemne rozwiązania układu równań:
Ćwiczenie 3
Wyznacz najmniejsze, nieujemne rozwiązania układu równań:
Ćwiczenie 4
Policz wartości funkcji Eulera:
- ,
- ,
- .
Ćwiczenie 5
Policz możliwie szybko:
- { mod},
- { mod},
- { mod}.
Ćwiczenie 6
Funkcja liczbowa określona na zbiorze jest multyplikatywna, jeśli dla dowolnych względnie pierwszych zachodzi
Widzieliśmy, że -Eulera jest multyplikatywna. Pokaż, że:
- funkcja Mobiusa jest multyplikatywna,
- jeśli funkcja jest multyplikatywna to też.
Ćwiczenie 7
Udowodnij, że liczba naturalna jest pierwsza wtedy i tylko wtedy, gdy .
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.