XIV OM - III - Zadanie 1

Zawody matematyczne:

XIV OM, 1962-1963

Etap:

III

Dowieść, że dwie liczby naturalne, których cyframi są same jedynki, są względnie pierwsze wtedy i tylko wtedy, gdy liczby ich cyfr są względnie pierwsze.

Rozwiązanie

Niech $J_m$ oznacza liczbę $m$ -cyfrową, której cyframi są same jedynki:

$ J_m= 10^{m-1} + 10^{m-2}+ \ldots + 10 + 1 = \frac{1}{9}(l0^m- 1). $

Dowód, który mamy przeprowadzić, oprzemy na dwóch własnościach liczby $J_m$ .

$\alpha$ ) Jeżeli $m$ jest podzielne przez $d$ ( $m$ , $d$ - liczby naturalne), to $J_m$ jest podzielne przez $J_d$ . Istotnie, jeśli $m = k \cdot d$ ( $k$ - liczba naturalna), to

$ J_m = J_{kd} = \frac{1}{9} \left[(10^d)^k - 1 \right] = \frac{1}{9} (10^d - 1) (10^{kd-d}+ 10^{kd-2d} + \ldots + 10^d + 1) = J_d \cdot M, $

gdzie liczba $M$ jest całkowita.

$\beta$ ) Jeżeli $m > n$ , to

$ J_m - J_n = \frac{1}{9}(10^m - 1) - \frac{1}{9} (10^n - 1) = \frac{1}{9}(10^{m-n}-1) \cdot 10^n = J_{m-n} - 10^n. $

Niech będą dane liczby $J_m$ i $J_n$ , gdzie $m > n > 1$

a) Dowód twierdzenia, że jeżeli $J_m$ i $J_n$ są względnie pierwsze, to $m$ i $n$ są też względnie pierwsze, jest natychmiastowy, gdyż według $\alpha$ ) jeżeli $d$ jest wspólnym dzielnikiem naturalnym liczb $m$ i $n$ , to $J_d$ jest wspólnym dzielnikiem liczb $J_m$ i $J_n$ .

b) Udowodnimy twierdzenie odwrotne. Przypuśćmy, że liczby naturalne $m$ i $n$ są względnie pierwsze. Stosując algorytm Euklidesa, tzn. dzieląc kolejno $m$ przez $m$ , $n$ przez otrzymaną resztę $r$ , resztę $r$ przez nową resztę $r_1$ itd. otrzymujemy reszty coraz mniejsze, więc dochodzimy węszcie do reszty równej zeru:

$ (1) \qquad \begin{array}{ccc} m = nq + r & \textrm{gdzie} & 0 < r < n \\ n = rq_1 + r_1 & \textrm{gdzie} & 0 < r_1 < r \\ r = r_1q_2 + r_2 & \textrm{gdzie} & 0 < r_2 < r_1 \\ \ldots \\ r_{k-2} = r_{k-1}q_k+ r_k & \textrm{gdzie} & 0 < r_k < r_{k-1}\\ r_{k-1} = r_kq_{k + 1} & & \end{array} $

Z ciągu równości (1) wynika, że liczba naturalna $r_k$ jest wspólnym dzielnikiem liczb $r_{k-1}, r_{k-2}, \ldots,r, n, m$ , zatem $r_k= 1$ .

Z pierwszej równości (1) wnioskujemy, na podstawie $\beta$ ), że

$ (2) \qquad J_m-J_{nq} = J_r \cdot 10^{nq}. $

Niech $D$ będzie wspólnym dzielnikiem naturalnym liczb $J_m$ i $J_n$ . Ponieważ $J_{nq}$ jest na mocy $\alpha)$ podzielne przez $J_n$ , więc $D$ jest według (2) również dzielnikiem liczby $J_r \cdot 10^{nq}$ . Liczba $10^{nq}$ nie ma innych dzielników pierwszych oprócz liczb $2$ i $5$ , które nie są dzielnikami liczby $J_m$ , więc $D$ jest względnie pierwsze z $10^{nq}$ . Zatem $D$ jest dzielnikiem $J_r$ .

W taki sam sposób, opierając się na następnych równościach (1), stwierdzimy kolejno, że $D$ jest dzielnikiem liczb $J_{r_1}, J_{r_2}, \ldots, J_{r_k}$ . Lecz $r_k = 1$ , więc

$ J_{r_k} = J_1 = 1; \textrm{stąd} D = 1. $

Znaczy to, że $J_m$ i $J_n$ są względnie pierwsze, co właśnie mieliśmy udowodnić.

Uwaga 1. Część b) powyższego dowodu można zastąpić rozumowaniem znacznie krótszym, korzystając z następującego znanego twierdzenia teorii liczb:

Jeżeli liczby naturalne $m$ i $n$ są względnie pierwsze, to istnieją takie liczby naturalne $x$ i $y$ , że

$ (3) \qquad mx - ny = 1. $

Zachodzi również twierdzenie odwrotne: jeżeli liczby naturalne $m$ , $n$ , $x$ , $y$ spełniają równanie (3), to $m$ i $n$ są względnie pierwsze. Z równości (3) wynika bowiem, że każdy wspólny dzielnik liczb $m$ i $n$ jest dzielnikiem liczby $1$ .

Załóżmy, że liczby naturalne $m$ , $n$ , są względnie pierwsze, wobec czego dla pewnych naturalnych liczb $x$ i $y$ zachodzi (3). Wówczas

$ J_{mx} - 10J_{ny} = \frac{1}{9}(10^{mx} - 1) - \frac{10}{9} (10^{ny} - 1) = \frac{1}{9}(10^{mx} - 10^{ny+1} + 9) = 1, $

a ponieważ według ( $\alpha$ ): $J_{mx} = J_m \cdot M$ oraz $J_{my} = J_m \cdot N$ , gdzie liczby $M$ i $N$ są naturalne, więc:

$ MJ_m - 10 \cdot NJ_n = 1, $

skąd wynika, że $J_m$ i $J_n$ są względnie pierwsze.

Uwaga 2. Dowód twierdzenia, cytowanego w uwadze 1, można wysnuć z ciągu równości (1). Podstawiając wartość $r$ z pierwszej równości do drugiej, następnie po tym podstawieniu wartość $r_1$ z drugiej równości do trzeciej itd. dochodzimy w końcu, uwzględniając że $r_k= 1$ , do równości postaci (3).

Uwaga 3. W powyższych rozumowaniach przyjęliśmy, że podstawą numeracji jest $10$ . Twierdzenie jest jednak prawdziwe dla dowolnej podstawy numeracji $g$ . Dowód pozostaje ten sam, z tym, że trzeba wszędzie $10$ zastąpić przez $g$ .