LIGA ZADANIOWA UMK W TORUNIU 2005/2006
ZADANIA PRZYGOTOWAWCZE DO ETAPU II
DLA KLAS II GIMNAZJUM

Zadanie 18:

Pewna liczba naturalna n przy dzieleniu przez 2000 i przy dzieleniu przez 2001 daje tę samą resztę 118. Jaka jest reszta z dzielenia liczby n przez 33?

Dane:
n - niewiadoma liczba (o której mowa w zadaniu)
n-118 - dzieli się przez 2001 i 2002

 W rozwiązaniu zadania skorzystam z

ZASADNICZEGO PRAWA ARYTMETYKI (ZPA):
Jeśli NWD(a,b)=1 i a|n i b|n to ab|n

Przedtem jednak pokażę, że największy wspólny dzielnik dwóch kolejnych liczb naturalnych n i n + 1 jest równy 1: NWD(n,n +1 ) = 1

n + 1 - n = 1

Niech d = NWD(n,n + 1)

Oczywiście d jest liczbą nauralną i d >0:

n = ad oraz n + 1 = bd

gdzie a i b są pewnymi liczbami całkowitymi. Zauwazmy, że

(n + 1) - (n) = 1

to znaczy:

bd - ad = 1

d ( b - a) = 1

Stąd d = 1 bo jedynym dzielnikiem naturalnym liczby 1 jest 1.
Teraz przechodzę do rozwiązania zadania: Z informacji o liczbie n wiemy, że

2001 | n - 118    i    2002 | n - 118

więc korzystając z Zasadniczego Prawa Arytmetyki

2001 × 2002 | n - 118

tzn., że istnieje liczba całkowita k, że n - 118 = 2001 × 2002 × k

n = 2001 × 2002 × k + 118

n = 3 × 667 × 2 × 7 × 11 × 13 × k + 3 × 33 + 19

n = 33 × 667 × 2 × 7 × 13 × k + 3 × 33 + 19

Odpowiedź: Reszta jest równa 19.

Agata Kwapisz