- LX OM
- LIX OM
- LVIII OM
- LVII OM
- LVI OM
- LV OM
- LIV OM
- LIII OM
- LII OM
- LI OM
- L OM
- XLIX OM
- XLVIII OM
- XLVIII OM - I etap
- XLVIII OM - I - Zadanie 1
- XLVIII OM - I - Zadanie 2
- XLVIII OM - I - Zadanie 3
- XLVIII OM - I - Zadanie 4
- XLVIII OM - I - Zadanie 5
- XLVIII OM - I - Zadanie 6
- XLVIII OM - I - Zadanie 7
- XLVIII OM - I - Zadanie 8
- XLVIII OM - I - Zadanie 9
- XLVIII OM - I - Zadanie 10
- XLVIII OM - I - Zadanie 11
- XLVIII OM - I - Zadanie 12
- XLVIII OM - II etap
- XLVIII OM - III etap
- XLVIII OM - I etap
- XLVII OM
- XLVI OM
- XLV OM
- XLIV OM
- XLIII OM
- XLII OM
- XLI OM
- XL OM
- XXXIX OM
- XXXVIII OM
- XXXVIII OM - I etap
- XXXVIII OM - I - Zadanie 1
- XXXVIII OM - I - Zadanie 2
- XXXVIII OM - I - Zadanie 3
- XXXVIII OM - I - Zadanie 4
- XXXVIII OM - I - Zadanie 5
- XXXVIII OM - I - Zadanie 6
- XXXVIII OM - I - Zadanie 7
- XXXVIII OM - I - Zadanie 8
- XXXVIII OM - I - Zadanie 9
- XXXVIII OM - I - Zadanie 10
- XXXVIII OM - I - Zadanie 11
- XXXVIII OM - I - Zadanie 12
- XXXVIII OM - II etap
- XXXVIII OM - III etap
- XXXVIII OM - I etap
- XXXVII OM
- XXXVII OM - I etap
- XXXVII OM - I - Zadanie 1
- XXXVII OM - I - Zadanie 2
- XXXVII OM - I - Zadanie 3
- XXXVII OM - I - Zadanie 4
- XXXVII OM - I - Zadanie 5
- XXXVII OM - I - Zadanie 6
- XXXVII OM - I - Zadanie 7
- XXXVII OM - I - Zadanie 8
- XXXVII OM - I - Zadanie 9
- XXXVII OM - I - Zadanie 10
- XXXVII OM - I - Zadanie 11
- XXXVII OM - I - Zadanie 12
- XXXVII OM - II etap
- XXXVII OM - III etap
- XXXVII OM - I etap
- XXXVI OM
- XXXV OM
- XXXIV OM
- XXXIII OM
- XXXIII OM - I etap
- XXXIII OM - I - Zadanie 1
- XXXIII OM - I - Zadanie 2
- XXXIII OM - I - Zadanie 3
- XXXIII OM - I - Zadanie 4
- XXXIII OM - I - Zadanie 5
- XXXIII OM - I - Zadanie 6
- XXXIII OM - I - Zadanie 7
- XXXIII OM - I - Zadanie 8
- XXXIII OM - I - Zadanie 9
- XXXIII OM - I - Zadanie 10
- XXXIII OM - I - Zadanie 11
- XXXIII OM - I - Zadanie 12
- XXXIII OM - II etap
- XXXIII OM - III etap
- XXXIII OM - I etap
- XXXII OM
- XXXI OM
- XXX OM
- XXIX OM
- XXVIII OM
- XXVII OM
- XXVI OM
- XXV OM
- XXIV OM
- XXIII OM
- XXII OM
- XXI OM
- XX OM
- XIX OM
- XVIII OM
- XVII OM
- XVI OM
- XV OM
- XIV OM
- XIII OM
- XII OM
- XI OM
- X OM
- IX OM
- VIII OM
- VII OM
- V OM
- VI OM
- IV OM
- III OM
- II OM
- I OM
- Skład komitetów Olimpiady
- Zawody stopnia I (przygotowawcze)
- Zadania z pierwszej olimpiady matematycznej
- I OM - B
- I OM - B - Zadanie 1
- I OM - B - Zadanie 2
- I OM - B - Zadanie 3
- I OM - B - Zadanie 4
- I OM - B - Zadanie 5
- I OM - B - Zadanie 6
- I OM - B - Zadanie 7
- I OM - B - Zadanie 8
- I OM - B - Zadanie 9
- I OM - B - Zadanie 10
- I OM - B - Zadanie 11
- I OM - B - Zadanie 12
- I OM - B - Zadanie 13
- I OM - B - Zadanie 14
- I OM - B - Zadanie 15
- I OM - B - Zadanie 16
- I OM - B - Zadanie 17
- I OM - B - Zadanie 18
- I OM - B - Zadanie 19
- I OM - B - Zadanie 20
- I OM - I etap
- I OM - II etap
- I OM - III etap
- I OM - B
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 oznacza liczbę
-cyfrową, której cyframi są same jedynki:
![]() |
Dowód, który mamy przeprowadzić, oprzemy na dwóch własnościach liczby .
) Jeżeli
jest podzielne przez
(
,
- liczby naturalne), to
jest podzielne przez
. Istotnie, jeśli
(
- liczba naturalna), to
![]() |
gdzie liczba jest całkowita.
) Jeżeli
, to
![]() |
Niech będą dane liczby i
, gdzie
a) Dowód twierdzenia, że jeżeli i
są względnie pierwsze, to
i
są też względnie pierwsze, jest natychmiastowy, gdyż według
) jeżeli
jest wspólnym dzielnikiem naturalnym liczb
i
, to
jest wspólnym dzielnikiem liczb
i
.
b) Udowodnimy twierdzenie odwrotne. Przypuśćmy, że liczby naturalne i
są względnie pierwsze. Stosując algorytm Euklidesa, tzn. dzieląc kolejno
przez
,
przez otrzymaną resztę
, resztę
przez nową resztę
itd. otrzymujemy reszty coraz mniejsze, więc dochodzimy węszcie do reszty równej zeru:
![]() |
Z ciągu równości (1) wynika, że liczba naturalna jest wspólnym dzielnikiem liczb
, zatem
.
Z pierwszej równości (1) wnioskujemy, na podstawie ), że
![]() |
Niech będzie wspólnym dzielnikiem naturalnym liczb
i
. Ponieważ
jest na mocy
podzielne przez
, więc
jest według (2) również dzielnikiem liczby
. Liczba
nie ma innych dzielników pierwszych oprócz liczb
i
, które nie są dzielnikami liczby
, więc
jest względnie pierwsze z
. Zatem
jest dzielnikiem
.
W taki sam sposób, opierając się na następnych równościach (1), stwierdzimy kolejno, że jest dzielnikiem liczb
. Lecz
, więc
![]() |
Znaczy to, że i
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 i
są względnie pierwsze, to istnieją takie liczby naturalne
i
, że
![]() |
Zachodzi również twierdzenie odwrotne: jeżeli liczby naturalne ,
,
,
spełniają równanie (3), to
i
są względnie pierwsze. Z równości (3) wynika bowiem, że każdy wspólny dzielnik liczb
i
jest dzielnikiem liczby
.
Załóżmy, że liczby naturalne ,
, są względnie pierwsze, wobec czego dla pewnych naturalnych liczb
i
zachodzi (3). Wówczas
![]() |
a ponieważ według ():
oraz
, gdzie liczby
i
są naturalne, więc:
![]() |
skąd wynika, że i
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ść z pierwszej równości do drugiej, następnie po tym podstawieniu wartość
z drugiej równości do trzeciej itd. dochodzimy w końcu, uwzględniając że
, do równości postaci (3).
Uwaga 3. W powyższych rozumowaniach przyjęliśmy, że podstawą numeracji jest . Twierdzenie jest jednak prawdziwe dla dowolnej podstawy numeracji
. Dowód pozostaje ten sam, z tym, że trzeba wszędzie
zastąpić przez
.
Komentarze
Dodaj nową odpowiedź