XIV OM - III - Zadanie 1

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:

\[<br /> J_m= 10^{m-1} + 10^{m-2}+ \ldots + 10 + 1 = \frac{1}{9}(l0^m- 1).<br /> \]

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

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

gdzie liczba $ M $ jest całkowita.

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

\[<br /> J_m - J_n = \frac{1}{9}(10^m - 1) - \frac{1}{9} (10^n - 1) =<br /> \frac{1}{9}(10^{m-n}-1) \cdot 10^n = J_{m-n} - 10^n.<br /> \]

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:

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

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

\[<br /> (2) \qquad J_m-J_{nq} = J_r \cdot 10^{nq}.<br /> \]

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

\[<br /> J_{r_k} = J_1 = 1; \textrm{stąd} D = 1.<br /> \]

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

\[<br /> (3) \qquad mx - ny = 1.<br /> \]

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

\[<br /> J_{mx} - 10J_{ny} = \frac{1}{9}(10^{mx} - 1) - \frac{10}{9} (10^{ny} - 1) =<br /> \frac{1}{9}(10^{mx} - 10^{ny+1} + 9) = 1,<br /> \]

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:

\[<br /> MJ_m - 10 \cdot NJ_n = 1,<br /> \]

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 $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź