Najmniejsza liczba, dwie ostatnie cyfry

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
mint18
Użytkownik
Użytkownik
Posty: 279
Rejestracja: 16 lip 2015, o 11:21
Płeć: Mężczyzna
Lokalizacja: Lub
Podziękował: 160 razy
Pomógł: 21 razy

Najmniejsza liczba, dwie ostatnie cyfry

Post autor: mint18 »

Wyznaczyć najmniejszą liczbę całkowitą \(\displaystyle{ n>13}\), taką że dwie ostatnie cyfry \(\displaystyle{ n^2}\) to \(\displaystyle{ 69}\).

Korzystam tu z kongruencji i doszedłem do tego, że \(\displaystyle{ n}\) w postaci \(\displaystyle{ 50k+13}\) spełniają warunek zadania, ale coś chyba robię nie tak, bo już \(\displaystyle{ 37}\) to spełnia, a nie jest w tej postaci.
Dlatego prosiłbym o całe rozwiązanie tego zadania.
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Najmniejsza liczba, dwie ostatnie cyfry

Post autor: Medea 2 »

A co powiesz na to, że liczby postaci \(\displaystyle{ 50 k \pm 13}\) spełniają tę kongruencję? Zaczęłabym od tego, że ostatnia cyfra (jedności) to \(\displaystyle{ 3}\) lub \(\displaystyle{ 7}\). Nie wiem, czy jest sens bawić się w to dalej. Jeżeli ostatnią cyfrą jest \(\displaystyle{ 7}\), to \(\displaystyle{ (10k + 7)^2 \equiv 49 + 40k \pmod {100}}\). Widać, że do \(\displaystyle{ 69}\) brakuje nam dwudziestki, co możemy uzyskać biorąc trzy czterdziestki (\(\displaystyle{ 3 \cdot 40 \equiv 20}\)), dwie lub jedna nie wystarczą. To daje \(\displaystyle{ 37}\). Jeżeli ostatnią cyfrą jest \(\displaystyle{ 3}\), to \(\displaystyle{ (10k + 3)^2 \equiv 60k + 9 \pmod {100}}\), więc \(\displaystyle{ k = 1}\) lub \(\displaystyle{ k = 11}\) (ale to nas nie interesuje).
ODPOWIEDZ