Oblicz mod 9!
Oblicz mod 9!
Wydaje mi się, że 9 możesz podnieść do dowolnej potęgi, a i tak otrzymasz liczbę podzielną przez 9, czyli wynik = 0.
-
Przemas O'Black
- Użytkownik
- Posty: 744
- Rejestracja: 7 lut 2009, o 18:30
- Płeć: Mężczyzna
- Podziękował: 69 razy
- Pomógł: 58 razy
Oblicz mod 9!
Dla wykładników naturalnych różnych od zera z pewnością tak jest.kate3 pisze:Wydaje mi się, że 9 możesz podnieść do dowolnej potęgi, a i tak otrzymasz liczbę podzielną przez 9, czyli wynik = 0.
-
Maciej87
- Użytkownik
- Posty: 377
- Rejestracja: 26 sty 2009, o 09:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 46 razy
Oblicz mod 9!
Otóż to właśnie.
Oznaczmy tą wielką liczbę przez \(\displaystyle{ x}\).
A więc bierzemy się do roboty i sprawdzamy co to za liczba
\(\displaystyle{ 9! = \left( \left( 2 \right) \right) ^{7} \left( \left( 3 \right)
\right) ^{4} \left( 5 \right) \left( 7 \right)}\).
Chytry plan jest taki: wyznaczymy reszty z dzielenia przez \(\displaystyle{ 2^7,3^4,5,7}\), a następnie wykorzystamy chińskie twierdzenie o resztach i dostaniemy resztę \(\displaystyle{ \mod 9!}\)
Resztę \(\displaystyle{ \mod 3^4}\) mamy załatwioną to \(\displaystyle{ x\equiv 0 \mod 3^4}\).
Teraz polecam taki lemat, dla liczby pierwszej \(\displaystyle{ p}\): \(\displaystyle{ a \equiv b \mod p \Rightarrow a^{p^{n}} \equiv b^{p^{n}} \mod p^{n+1}}\)
Stąd \(\displaystyle{ 9 \equiv 1 \mod 2 \Rightarrow 9^2 \equiv 1^2 \equiv 1 \mod 2^2 \ldots \Rightarrow 9^{2^6}\equiv 1 \mod 2^7}\). Nasz wykładnik jest postaci \(\displaystyle{ 2^6\cdot k}\) zatem \(\displaystyle{ 9^{2^6\cdot k} \equiv 1^{k} \equiv 1 \mod 2^{7}}\). Zatem \(\displaystyle{ x\equiv 1 \mod 2^7}\)
Dalej \(\displaystyle{ 9\equiv -1 \mod 5}\) a wykładnik jest parzysty, \(\displaystyle{ x \equiv 1 \mod 5}\)
Na koniec \(\displaystyle{ 9\equiv 2 \mod 7}\). Wykładnik \(\displaystyle{ 8^{7^{6^{5^{4^{3^{2}}}}}}}\) jest parzysty i \(\displaystyle{ \mod 3}\) daje resztę \(\displaystyle{ -1}\) zatem jest postaci \(\displaystyle{ 6k+2}\).
Ponieważ \(\displaystyle{ 2^{6}\equiv 1 \mod 7}\) to \(\displaystyle{ x\equiv 2^{6k+2} \equiv \left(2^{6}\right)^{k} \cdot 2^2 \equiv 1\cdot 2^2 \mod 7}\) czyli \(\displaystyle{ x \equiv 4 \mod 7}\)
Oznaczmy tą wielką liczbę przez \(\displaystyle{ x}\).
A więc bierzemy się do roboty i sprawdzamy co to za liczba
\(\displaystyle{ 9! = \left( \left( 2 \right) \right) ^{7} \left( \left( 3 \right)
\right) ^{4} \left( 5 \right) \left( 7 \right)}\).
Chytry plan jest taki: wyznaczymy reszty z dzielenia przez \(\displaystyle{ 2^7,3^4,5,7}\), a następnie wykorzystamy chińskie twierdzenie o resztach i dostaniemy resztę \(\displaystyle{ \mod 9!}\)
Resztę \(\displaystyle{ \mod 3^4}\) mamy załatwioną to \(\displaystyle{ x\equiv 0 \mod 3^4}\).
Teraz polecam taki lemat, dla liczby pierwszej \(\displaystyle{ p}\): \(\displaystyle{ a \equiv b \mod p \Rightarrow a^{p^{n}} \equiv b^{p^{n}} \mod p^{n+1}}\)
Stąd \(\displaystyle{ 9 \equiv 1 \mod 2 \Rightarrow 9^2 \equiv 1^2 \equiv 1 \mod 2^2 \ldots \Rightarrow 9^{2^6}\equiv 1 \mod 2^7}\). Nasz wykładnik jest postaci \(\displaystyle{ 2^6\cdot k}\) zatem \(\displaystyle{ 9^{2^6\cdot k} \equiv 1^{k} \equiv 1 \mod 2^{7}}\). Zatem \(\displaystyle{ x\equiv 1 \mod 2^7}\)
Dalej \(\displaystyle{ 9\equiv -1 \mod 5}\) a wykładnik jest parzysty, \(\displaystyle{ x \equiv 1 \mod 5}\)
Na koniec \(\displaystyle{ 9\equiv 2 \mod 7}\). Wykładnik \(\displaystyle{ 8^{7^{6^{5^{4^{3^{2}}}}}}}\) jest parzysty i \(\displaystyle{ \mod 3}\) daje resztę \(\displaystyle{ -1}\) zatem jest postaci \(\displaystyle{ 6k+2}\).
Ponieważ \(\displaystyle{ 2^{6}\equiv 1 \mod 7}\) to \(\displaystyle{ x\equiv 2^{6k+2} \equiv \left(2^{6}\right)^{k} \cdot 2^2 \equiv 1\cdot 2^2 \mod 7}\) czyli \(\displaystyle{ x \equiv 4 \mod 7}\)