Matematyka dyskretna 1/Ćwiczenia 11: Teoria liczb II: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
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ń:

  • 21x365,
  • 4x76,
  • 3x3327,
  • 3x10059,
  • 2x43,
  • 16x248.
Rozwiązanie

Ćwiczenie 2

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


x32,x53,x114,x165


Rozwiązanie

Ćwiczenie 3

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


x3123,x127,x3512.


Rozwiązanie

Ćwiczenie 4

Policz wartości funkcji Eulera:

  • φ(10),
  • φ(100),
  • φ(1000).
Rozwiązanie

Ćwiczenie 5

Policz możliwie szybko:

  • 1675{ mod}35,
  • 2100{ mod}3,
  • 2155{ mod}32.
Rozwiązanie

Ćwiczenie 6

Funkcja f liczbowa określona na zbiorze jest multyplikatywna, jeśli dla dowolnych względnie pierwszych m,n zachodzi


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


Widzieliśmy, że φ-Eulera jest multyplikatywna. Pokaż, że:

  1. funkcja μ Mobiusa jest multyplikatywna,
  2. jeśli funkcja f(n)=d|ng(d) jest multyplikatywna to g(n) też.
Rozwiązanie

Ćwiczenie 7

Udowodnij, że liczba naturalna n>1 jest pierwsza wtedy i tylko wtedy, gdy (n1)!n1.

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
Rozwiązanie