XXXIV OM - III - Zadanie 4

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Udowodnić, że jeżeli liczby naturalne $a, b, c, d$ spełniają równość $ab = cd$ , to

$ \frac{\mathrm{NWD}(a, c)\cdot \mathrm{NWD}(a, d)}{\mathrm{NWD}(a, b, c, d)} = a. $

Rozwiązanie

Udowodnimy najpierw, że dla dowolnych liczb naturalnych $k$ , $j$ , $m$ , $n$

$ (1) \qquad \mathrm{NWD}(k,l) \cdot \mathrm{NWD} (m, n) = \mathrm{NWD} (km, kn, lm, ln). $

Jeśli liczba pierwsza $p$ spełnia relacje $p^\alpha | \mathrm{NWD} (k, l)$ oraz $p^\beta | \mathrm{NWD} (m,n)$ , to $p^\alpha | k$ , $p^\alpha | l$ , $p^\beta | m$ , $p^\beta | n$ , więc $p^{\alpha+\beta}$ dzieli każdą z liczb $km$ , $kn$ , $lm$ , $ln$ . Stąd $p^{\alpha+\beta} | \mathrm{NWD} (km, kn, lm, ln)$ . Wobec tego $\mathrm{NWD} (k, l) \cdot \mathrm{NWD} (m, n) | \mathrm{NWD} (km, kn, lm, ln)$ .

Jeśli $p^\gamma | \mathrm{NWD} (km, kn, lm, ln)$ oraz $p^\alpha | \mathrm{NWD} (k, l)$ , ale $p^{\alpha + 1} not \mid \mathrm{NWD} (k, l)$ , to jedna z liczb $k$ , $l$ nie dzieli się przez $p^{\alpha+1}$ , np. $k= p^\alpha \cdot k_1$ , $p \not \mid k_1$ . Ponieważ $p^\gamma | km$ , $p^\gamma | kn$ , więc $p^{\gamma \cdot \alpha} | \mathrm{NWD}(m, n)$ .

Wynika stąd, że $p^\gamma | \mathrm{NWD} (k, l) \cdot \mathrm{NWD} (m, n)$ , więc $\mathrm{NWD} (km, kn, lm, ln) | \mathrm{NWD} (k, l) \cdot \mathrm{NWD} (m, n)$ .

Tym samym równość (1) została udowodniona. Podstawiając w tej równości $k = a$ , $l = c$ , $m = a$ , $n= d$ otrzymamy

$ \mathrm{NWD}(a, c) \cdot \mathrm{NWD}(a,d)= \mathrm{NWD} (a^2, ad, ac, cd). $

Wobec założenia $cd = ab$ dostajemy stąd

$ \mathrm{NWD} (a, c) \cdot \mathrm{NWD} (a, d) = \mathrm{NWD} (a^2, ad, ac, ab) = a \cdot \mathrm{NWD} (a, d, c, b) = a \cdot \mathrm{NWD} (a, b, c, d). $