Wyznaczyć dwie ostatnie cyfry liczby 3^128 Weronika: Wyznaczyć dwie ostatnie cyfry liczby 3¹28 jakie najlepsze twierdzenie do tego ? Eulera ? Może ktoś pomóc w rozwiązaniu ? Pozdrawiam

a7: wskazówki https://matematykaszkolna.pl/forum/259941.html przykład na str. 5 http://knm.katowice.pl/licea/kolko/14.11.2011_beata_lojan/pliki/kongruencje.pdf

ICSP: 3¹²⁸ = 9⁶⁴ = 81³² = (10 * 8 + 1)³² = 10k + 1 , k ∊ Z ostatnie przejście wynika z wzoru dwumianowego Newtona.

Adamm: 3¹²⁸ ≡ (−1)¹²⁸ = 1 (mod 4) φ(25) = 20 3¹²⁸ ≡ 3⁸ = 9*(27)² ≡ 36 ≡ 11 (mod 25) ⇒ 3¹²⁸ przystaje do 11, 36, 61, 86 mod 100 ale z tego że przystaje 1 mod 4 3¹²⁸ ≡ 61 (mod 100)

ICSP: dwie ostatnie a nie jedną

Mila: 100=2²*5² φ(100)=40 3⁴⁰=1(mod100) 3¹²⁸=(3⁴⁰)³*3⁸ 3⁴=81 81²=6561 3¹²⁸≡1(mod100)* 61 (mod100)≡61(mod100)

Weronika: @Mila nie rozumiem tylko dlaczego obliczyłaś w kolejnych krokach 3⁴ i 81² i końcowy wynik również jakbyś mogła wytłumaczyć (1(mod100)*61(mod100)

Mila: (3⁴)²=3⁸ 3¹²⁸= (3⁴⁰)³)*3⁸ (3⁴⁰)³≡1(mod100) 3⁸≡61(mod100) mnożymy stronami i masz jw.

Weronika: to jeszcze dopytam jak przy tak duże potędze jak 3¹²⁰ obliczyć mod z tego. Konkretnie chodzi mi tylko już o ten wpis (3⁴⁰)³= 1(mod100) na pewno jest jakiś szybki sposób

Mila: Funkcja Eulera. http://www.math.edu.pl/narzedzia.php?opcja=funkcja-eulera Twierdzenie Eulera. https://pl.wikipedia.org/wiki/Twierdzenie_Eulera_(teoria_liczb) W skrócie: Jeżeli liczby n i a są względnie pierwsze to: a^φ(n)≡1(modn) W zadaniu: a=3, n=100 , NWD(3,100)=1 100=2²*5²

	1		1		1		4
φ(100)=100*(1−		)*(1−		)=100*		*		=40
	2		5		2		5

⇒ 3^φ(100)=3⁴⁰≡1(mod 100)

Marek: to jest to samo (3⁴⁰)³ = 1 ( mod 100) co (3⁴⁰)=1(mod100) ?

Mila: Jeżeli masz liczbę np. 201≡(mod100) to 201²≡1(mod100) i do każdej potęgi Z faktu (3⁴⁰)≡1(mod100)⇒(3⁴⁰)³≡1(mod100)