/Konkursy/Zadania/Liczby/Całkowite/Podzielność

Zadanie nr 9401725

Dane są różne liczby pierwsze p ,q oraz takie dodatnie liczby całkowite a,b , że liczba aq daję resztę 1 przy dzieleniu przez p , a liczba bp daje resztę 1 przy dzieleniu przez q . Wykaż, że

a-+ b-> 1. p q
Wersja PDF

Rozwiązanie

Wiemy, że aq = kp+ 1 i bp = lq + 1 dla pewnych liczb naturalnych k i l . To oznacza, że

aq+ bp − 1 = aq + lq = q (a+ l)

oraz

aq+ bp− 1 = bp + (aq − 1 ) = bp + kp = p(b+ k).

To oznacza, że liczba aq + bp − 1 dzieli się zarówno przez p jak i przez q . W takim razie dzieli się też przez pq (bo p i q są dwoma różnymi liczbami pierwszymi). Zatem

aq+ bp − 1 ------------≥ 1 pq a- b- 1-- p + q − pq ≥ 1 a-+ b-≥ 1+ -1-> 1. p q pq
Wersja PDF