Twierdzenie Eulera i reszta z dzielenia

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
wodeczka94
Dopiero zaczynam
Dopiero zaczynam
Posty: 24
Rejestracja: 24 lis 2014, 16:45
Podziękowania: 4 razy
Płeć:

Twierdzenie Eulera i reszta z dzielenia

Post autor: wodeczka94 » 20 kwie 2015, 19:42

Cześć ! Muszę posługując się twierdzeniem Eulera obliczyć resztę z dzielenia \(7^{2014}\) przez \(18\)

Kompletnie tego nie rozumiem, tego fi itp itd. Mógbły ktoś mi to jakoś wytłumaczyć? Byłbym bardzo wdzięczny :)

Pozdrawiam :)

sebnorth
Stały bywalec
Stały bywalec
Posty: 871
Rejestracja: 11 gru 2010, 18:46
Lokalizacja: Puck i Trójmiasto
Otrzymane podziękowania: 413 razy
Płeć:

Post autor: sebnorth » 21 kwie 2015, 00:40

najpierw teoria z wiki:

In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that if \(n\) and \(a\) are coprime positive integers, then

\(a^{\varphi (n)} \equiv 1 \pmod{n}\)

where \(\varphi(n)\) is Euler's totient function

In number theory, Euler's phi function (or Euler's totient function), denoted as \(\varphi(n)\) or \(\phi(n)\), is an arithmetic function that counts the positive integers less than or equal to \(n\) that are relatively prime to \(n\)

plus wzór:

\(\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right),\)

where the product is over the distinct prime numbers dividing \(n\).

zastosowanie teorii do naszego zadania:

\(\phi(18) = 18\cdot(1 - \frac{1}{2} ) \cdot(1 - \frac{1}{3} ) = 6\)

\(a = 7, n = 18\)

\(7^6 \equiv 1 \pmod{18}\)

\(2014 = 6 \cdot 335 + 4\)

\(7^{2010} \equiv 1 \pmod{18}\)

\(7^2 \equiv -5 \pmod{18}\)

\(7^4 \equiv 25 \pmod{18}\)

\(25 \equiv 7 \pmod{18}\)

\(7^4 \equiv 7 \pmod{18}\)

\(7^{2014} \equiv 7 \pmod{18}\)