Trener OMJ

Zadania

Nauka

Zadanie 3

2011
Etap III
★★★★☆
Teoria liczb
Największy wspólny dzielnik

Powiązane zadania:

Zad. 2 (2010)
Zad. 3 (2016)
Zad. 1 (2011)
Treść zadania
Dane są takie dodatnie liczby całkowite aa, bb, że iloczyn abab jest podzielny przez sumę a+ba + b. Niech dd będzie największym wspólnym dzielnikiem liczb aa i bb. Udowodnij, że d⩾a+b.d \geqslant \sqrt{a+b}.
Zadania PDFRozwiązania PDF
Zgłoś błąd
Umiejętności (3)
Wymagane umiejętności:
Podzielność
Rozkład na czynniki pierwsze
Zdobywane umiejętności:
Podzielność
Wskazówki (0/4)
Wskazówka 1
Spróbuj zapisać liczby aa i bb za pomocą ich największego wspólnego dzielnika dd. Jeśli d=NWD(a,b)d = \text{NWD}(a, b), to a=d⋅ma = d \cdot m i b=d⋅nb = d \cdot n dla pewnych liczb całkowitych mm, nn. Jaką własność mają mm i nn?
Wskazówka 2
Podstaw a=dma = dm i b=dnb = dn (gdzie NWD(m,n)=1\text{NWD}(m, n) = 1) do warunku podzielności abab przez a+ba + b. Przekształć wyrażenie i zastanów się, co wynika z tego, że (a+b)∣ab(a+b) \mid ab.
Wskazówka 3
Po podstawieniu otrzymasz, że (m+n)∣d⋅m⋅n(m + n) \mid d \cdot m \cdot n. Wykorzystaj fakt, że NWD(m,n)=1\text{NWD}(m, n) = 1, aby pokazać, że (m+n)∣d(m+n) \mid d. Jaki wniosek możesz wyciągnąć o wielkości dd?
Wskazówka 4
Skoro (m+n)∣d(m + n) \mid d, to d≥m+nd \geq m + n. Teraz zauważ, że a+b=d(m+n)a + b = d(m + n), więc d≥m+nd \geq m + n oznacza d2≥d(m+n)=a+bd^2 \geq d(m+n) = a + b. Stąd wyprowadź końcową nierówność.
Prześlij rozwiązanie

Zaloguj się, aby przesłać swoje rozwiązanie

Zaloguj się