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
Twierdzenie Eulera i reszta z dzielenia
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Dopiero zaczynam
- Posty: 24
- Rejestracja: 24 lis 2014, 15:45
- Podziękowania: 4 razy
- Płeć:
-
- Stały bywalec
- Posty: 871
- Rejestracja: 11 gru 2010, 17:46
- Lokalizacja: Puck i Trójmiasto
- Otrzymane podziękowania: 415 razy
- Płeć:
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}\)
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}\)