Kongruencje Rurek: Czy ktoś życzliwy mógłby mi wytłumaczyć jak dziecku, jak się używa przytawania liczb modulo i pomógł zrobić zadanie: Udowodnić, że liczba 93⁹³ − 33³³ dzieli się przez 10 ?

Adamm: 93⁹³−33³³ φ(10)=4 gdzie φ(n) to https://pl.wikipedia.org/wiki/Funkcja_%CF%86 z tw. Eulera https://pl.wikipedia.org/wiki/Twierdzenie_Eulera_(teoria_liczb) mamy 93⁹³−33³³≡93−33=60≡0 mod 10

Adamm: trochę więcej wyjaśnień liczby względnie pierwsze to takie które nie mają wspólnych dzielników np., 2 oraz 9 są względnie pierwsze, 35 i 10 już nie bo obie dzielą się przez 5 φ(10)=4 ponieważ liczby mniejsze od 10 to 1, 2, 3, 4, 5, 6, 7, 8, 9 z czego względnie pierwsze z 10 to 1, 3, 7, 9, zatem φ(10)=4 93⁹³=93^4*23+1=93*(93⁴)²³ korzystając z własności a≡b mod n oraz c≡d mod n to a*c≡b*d mod n mamy 93⁴≡1 więc 93⁴*93⁴≡1 itd. zatem (93⁴)²³≡1 oraz 93*(93⁴)²³≡93 podobnie mamy z drugim reszty raczej nie muszę tłumaczyć

Mila: 93⁹³−33³³=(3*31)⁹³−(3*11)³³= =3⁹³*31⁹³−3³³*11³³ −−−−−−−−−−−−−−−−−−−− 31⁹³≡1 (mod10) 11³³≡1 (mod10) 3⁴=81≡(mod10) 3⁹³=(3⁴)²³*3≡3(mod10) 3³³=(3⁴)⁸*3≡3(mod10) 3⁹³*31⁹³−3³³*11³³≡3(mod10)−3(mod10)≡0(mod3)