Strona 1 z 1
Twierdzenie Eulera i reszta z dzielenia
: 20 kwie 2015, 19:42
autor: wodeczka94
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
: 21 kwie 2015, 00:40
autor: sebnorth
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}\)