Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Zadania z teorii liczb - poziom łatwy cz.2


  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
4 odpowiedzi w tym temacie

#1 Arczi

Arczi

    Operator całkujący

  • Redaktor
  • 340 postów
104
Pomocnik I
  • Płeć:Mężczyzna

Napisano 16.02.2010 - 19:13

Zadanie 1
Niech p będzie liczbą pierwszą większą niż 5. Udowodnij, że p-4 nie może być czwartą potęgą liczby całkowitej.


Zadanie 2
Udowodnij, że dla dowolnej liczby całkowitej n większej od 1, liczba n^5+n^4+1 jest złożona.


Zadanie 3
Znajdź wszystkie liczby całkowite p i q takie, że pq dzieli iloczyn (5^p-2^p)(5^q-2^q).
  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1008
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 16.02.2010 - 19:31

Póki co:

Ad.1

Załóżmy że dla pewnego n mamy n^2-2n+2=1 czyli n=1. Ale wtedy p=5 a to jest sprzeczne z warunkiem n^5+n^4+1 jest liczbą złożoną.

  • 0

#3 Arczi

Arczi

    Operator całkujący

  • Redaktor
  • 340 postów
104
Pomocnik I
  • Płeć:Mężczyzna

Napisano 07.07.2010 - 18:28

Wskazówka do zadania 3.

Należy skorzystać z Małego Twierdzenia Fermata oraz z następującego faktu:

Niech m będzie dodatnią liczbą całkowitą oraz niech a i b będą liczbami całkowitymi względnie pierwszymi z m. Jeśli x oraz y są to takie liczby całkowite, że

WYNIK:

Rozwiązaniem są pary: (3,3), (3,13) oraz (13,3).
  • 0

#4 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1008
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 09.07.2010 - 18:38

W treści zadania 3. nie ma nic o pierwszości liczb p i q, więc teoretycznie (p,q)=(1,1) powinno być rozwiązaniem, ale ze wskazówki wiemy, że nie jest. Wobec tego przyjmuję, że w treści zadania jest błąd i liczby p=3 to oczywiście musi być też q=3.

Jeśli p|5^q-2^q.

Ale z MTF wiemy też, że p|5^{p-1}-2^{p-1}.

Na mocy faktu ze wskazówki możemy zapisać, że q|p-1.

Teraz jeśli q=3 to p=13.

Jeśli zaś q>3 to podobnie jak poprzednio dochodzimy do wniosku, że q|5^{NWD(p,q-1)}-2^{NWD(p,q-1)}.

Ale p>q-1 więc NWD(p,q-1)=1 czyli q|3. Sprzeczność z założeniem q>3.

Podsumowując w tym przypadku mamy dwa rozwiązania: k i l, że kx+ly=NWD(x, \, y).

Wobec tego skoro a^x \, \eq \, b^x \ \text{mod m} to również a^{kx} \, \eq \, b^{kx} \ \text{mod m}.

Podobnie dochodzimy do wniosku, że a^{ly} \, \eq \, b^{ly} \ \text{mod m}.

W takim razie mnożąc stronami dwie ostatnie kongruencje dostajemy tezę.

Później miałem co prawda taką refleksję, że ten dowód nie jest poprawny, bo kongruencje można podnosić stronami do potęg o wykładniku naturalnym, a przecież jedna z liczb k, \, l będzie ujemna, ale już sobie z tym poradziłem, dowód można łatwo naprawić ;)

Jeśli wszystko jest ok, to proszę o kolejny zestaw "łatwych" :)
  • 0

#5 Arczi

Arczi

    Operator całkujący

  • Redaktor
  • 340 postów
104
Pomocnik I
  • Płeć:Mężczyzna

Napisano 09.07.2010 - 20:06

Słuszna uwaga ;) Nie liczby całkowite, a liczby pierwsze. Drobna, ale istotna pomyłka w tłumaczeniu.
  • 0