Przykładowe zadania z teorii liczb
I. Podzielność liczb całkowitych
1. Liczba a = 23461 przy dzieleniu przez pewną liczbę dodatnią całkowitą b daje iloraz k =
825 i resztÄ™ r. Znalez
ć dzielnik b oraz resztę r.
RozwiÄ…zanie.
a = 23461 = 825 " b + r, 0 < r < b. StÄ…d
361- r
b = 28 + ,
825
Liczba b musi być liczbą całkowitą dodatnią, zaś reszta r musi być dodatnia mniejsza od
825. Wynika stąd, że 361  r = 0. Otrzymujemy zatem b = 28, r = 361.
2. Pokazać, że n5  n, gdzie n jest liczb naturalną, jest podzielne przez 30.
RozwiÄ…zanie.
n5  n = (n  1) n (n + 1) (n2 + 1) = (n  1) n (n + 1) [(n2  4) + 5] =
= (n  2) (n  1) n (n + 1) (n + 2) + 5 (n  1) n (n + 1).
Każdy ze składników otrzymanej sumy jest podzielny przez 30, gdyż iloczyn k
następujących po sobie liczb naturalnych jest podzielny przez k!. Istotnie,
n(n - 1)(n - 2)...(n - k + 1)
k n
ëÅ‚ öÅ‚
Cn = =
ìÅ‚ ÷Å‚
k
íÅ‚ Å‚Å‚
1Å" 2 Å" 3Å" ...Å" k
jest liczbą całkowitą i dlatego rozważana wcześniej suma jest podzielna przez 30, a to
oznacza, że 30 dzieli n5  n.
3. Pokazać, że mn (m4  n4), gdzie m i n są liczbami naturalnymi, dzieli się przez 30.
RozwiÄ…zanie.
Zauważmy, że
mn (m4  n4) = n (m5 - m)  m(n5  n),
a jak było pokazane w przykładzie 2, m5  m dzieli się przez 30.
4. Pewna liczba sześciocyfrowa a kończy się cyfrą 5. Jeśli tę cyfrę przestawimy na miejsce
pierwsze ze strony lewej, to otrzymamy nowa liczbę, cztery razy większą od poprzedniej.
Znalez
ć liczbę a.
RozwiÄ…zanie.
Niech szukaną liczbą będzie 10 x + 5. Przestawiając cyfrę 5 na miejsce pierwsze,
otrzymujemy liczbÄ™ 5 Å" 105 + x.
Z warunków zadania wynika, że 5 Å" 105 + x = 4 (10 x + 5). StÄ…d x = 12820.
Zatem szukanÄ… liczbÄ… jest 128205.
5. Znalez
ć sumę n wyrazów ciągu S = 1 + 11 + 111 + ... + 11...1 (S jest sumą n
n n
składników).
RozwiÄ…zanie.
S = 1 + 11 + 111 + ... + 11..1 =
n
10 - 1 102 - 1 10n - 1 1
+ + ... + = (10 + 102 + ... + 10n - n)
9 9 9 9
ëÅ‚ öÅ‚
1 1- 10n ÷Å‚ 1 1
ìÅ‚
= 10 - n÷Å‚ = (- 10 + 10n+ 1 + 9n) = (10n+ 1 + 9n - 10.)
ìÅ‚
9 - 9 81 81
íÅ‚ Å‚Å‚
6. Znalez
ć wszystkie liczby całkowite x `" 3 takie, że x  3 dzieli x3  1.
RozwiÄ…zanie.
Połóżmy x  3 = t. Wtedy x = t + 3, x3  3 = (t +3)3  3. Jeśli x -3 dzieli x3-3 wtedy i
tylko wtedy gdy t dzieli (t + 3)3  3.
Ale
(t + 3)3  3 = t3  9 t2 + 27 t  24.
Zatem t dzieli (t + 3)3  3 wtedy i tylko wtedy gdy t dzieli 24, a więc t jest jedną z liczb
Ä…1, Ä…2, Ä…3, Ä…4, Ä…6, Ä…8, Ä…12, Ä…24. StÄ…d dla
x = t + 3 otrzymujemy: -21, -9, -5, -3, -1, 0, 1, 2, 4, 5, 6, 7, 9, 11, 15, 27.
7. Pokazać, że dla liczby naturalnej n, liczby n5 oraz n mają takie same cyfry jedności.
RozwiÄ…zanie.
W przykładzie 2 zostało pokazane, że liczba n5  n jest podzielna przez 30. Skoro jest
podzielna przez 30, to jest też podzielna przez 10. Zatem liczby n5 oraz n muszą mieć
takie same cyfry jedności.
8. Wykazać, że kwadrat każdej liczby całkowitej nieparzystej jest postaci 8 k + 1, gdzie k
jest dowolną liczbą całkowitą.
RozwiÄ…zanie.
Dowolną liczbę całkowitą można zapisać w postaci:
4q + 0, 4q + 1, 4 q + 2, 4 q + 3, gdzie q jest liczba całkowitą.
Liczby nieparzyste mają postać 4q + 1 lub 4q + 3. Policzmy kwadraty liczb nieparzystych:
(4q + 1)2 = 8 (2q2 + q) + 1 = 8 k + 1
1
(4q + 3)2 = 8 (2q2 + 3q + 1) + 1 = 8 k + 1,
2
gdzie k = 2q2 + q, a k = 2q2 + 3q + 1.
1 2
9. Dowieść, że dla naturalnych n, n2 dzieli (n + 1)n  1.
n n n
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
n
(1+ n) = 1+ ìÅ‚ ÷Å‚ n + ìÅ‚ ÷Å‚ n2 + ... + ìÅ‚ ÷Å‚ nn
ìÅ‚ ìÅ‚ ìÅ‚
1÷Å‚ 2÷Å‚ n÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
RozwiÄ…zanie.
Dla n = 1 twierdzenie jest oczywiście prawdziwe. Załóżmy, że n > 1 i policzmy n-tą
potęgę liczby n + 1.
Zauważmy, że wszystkie składniki w powyższej sumie, poczynając od trzeciego, zawierają n
w potędze większej lub równej 2, a drugim składnikiem jest n2. Zatem jeśli od rozważanej
sumy odejmiemy 1, to różnica będzie podzielna przez n2.
Algorytm Euklidesa. Równania diofantyczne. Największy wspólny dzielnik, najmniejsza
wspólna wielokrotność
1. StosujÄ…c algorytm Euklidesa znalez
ć największy wspólny dzielnik liczb 42823 i 6409.
RozwiÄ…zanie.
Zastosujmy algorytm Euklidesa
42823 = 6 Å" 6409 + 4369 (42823, 6409) =
6409 = 1 Å" 4369 + 2040 = (6409, 4369) =
4369 = 2 Å" 2040 + 289 = (4369, 2040)=
2040 = 7 Å" 289 + 17 = (2040, 289) =
289 = 17 Å" 17 = ( 289, 17) = 17.
2. Znalez
ć parę liczb całkowitych (x , y ) spełniających związek
o o
42823 x + 6409 y = 17.
o o
RozwiÄ…zanie.
W przykładzie 10, przy pomocy algorytmu Euklidesa został policzony największy
wspólny dzielnik liczb 42823 oraz 6409. Dzielnik ten jest równy 17 i jest podzielnikiem
wyrazu wolnego, który tu jest również równy 17. Zatem poszukiwane liczby x i y
o o
istniejÄ…. Wykorzystajmy algorytm Euklidesa do znalezienia liczb x , y Liczmy kolejno
o o.
17 = 2040  7 Å" 289 =
= 2040  7 (4369 - 2 Å" 2040) =
= -7 Å" 4369 + 15 Å" 2040 =
= -7 Å" 4369 + 15 (6409  4369) =
= -22 Å" 4369 + 15 Å" 6409 =
= - 22 (42823  6 Å" 6409) + 15 Å"6409 =
= - 22 Å" 42823 + 147 Å" 6409.
Zatem x = - 22, y =147.
o o
3. Rozwiązać w liczbach całkowitych następujące równanie
(* ) 42823 x + 6409 y = 68.
RozwiÄ…zanie.
Jeśli równanie a x + b y = c, gdzie a, b, c są liczbami całkowitymi, jest rozwiązalne w
liczbach całkowitych, to posiada ono nieskończenie wiele rozwiązań. Jeśli jednym z nich jest
para liczb całkowitych (x , y ), to wszystkie rozwiązania dane są wzorami
o o
x = x + b t , y = y t,
o 1 o- a
1
gdzie
a b
a1 = , b1 = .
(a,b) (a,b)
a t jest dowolną liczbą całkowitą.
Rozważane równanie posiada rozwiązanie w liczbach całkowitych , gdyż największy
wspólny dzielnik (42823, 6409) jest równy 17, a więc jest podzielnikiem liczby 68.
W przykładzie 11 zostało pokazane, że
42823 Å" ( -22) + 6409 Å" 147 = 17.
Pomnóżmy obie strony tej równości przez 4. Otrzymujemy wówczas
42823 Å" (-22 Å" 4) + 6409 Å" (147 Å" 4) = 68.
StÄ…d x = -88, y = 588.
o o
Zatem wszystkie rozwiązania równania (*) dane są wzorami
x = - 88 + 377 t, y = 588  2519 t,
gdzie t jest dowolną liczbą całkowitą.
Równania nieoznaczone możemy rozwiązywać również innymi metodami. Niekoniecznie
musimy się posługiwać przy ich rozwiązywaniu algorytmem Euklidesa.
4. Rozwiązać w liczbach całkowitych następujące równanie nieoznaczone
7 x  8 y = 44.
RozwiÄ…zanie.
Równanie posiada rozwiązanie, gdyż liczby 7 i 8 są względnie pierwsze.
Ich największy wspólny dzielnik jest równy 1, a więc jest podzielnikiem liczby 44.
Wyznaczmy x:
44 + 8y
x =
7
Podstawmy za y kolejno y = 0, 1, 2, ..., 5.
Dla y = 5 otrzymujemy x = 12, a zatem
x = 12 + 8 t,
y = 5 + 7 t,
gdzie t jest dowolną liczbą całkowitą.
5. Rozwiązać w liczbach całkowitych równanie
14 x + 28 y = 39.
RozwiÄ…zanie.
Równanie nie posiada rozwiązania w liczbach całkowitych, gdyż największy wspólny
dzielnik (14, 28) = 14, a liczba 14 nie jest podzielnikiem liczby 39.
6. Rozwiązać w liczbach całkowitych równanie
17 x + 39 y = 83.
RozwiÄ…zanie.
Liczby 17 oraz 39 są względnie pierwsze, zatem nasze równanie posiada rozwiązanie w
liczbach całkowitych. Wyliczmy x:
83 - 39y 15 - 5y 5(3 - y)
x = = 4 - 2y + = 4 - 2y + .
17 17 17
Liczba x jest liczbą całkowitą wtedy i tylko wtedy, gdy y = 3  17 t, gdzie t jest liczbą
całkowitą.
Rozwiązania równania mają zatem postać:
x = -2 + 39 t,
y = 3  17 t,
gdzie t jest dowolną liczbą całkowitą
7. Rozwiązać w liczbach naturalnych następujące równanie
7 x  13 y = 44.
RozwiÄ…zanie.
Liczby 7 i 13 są względnie pierwsze, zatem poszukiwanie rozwiązań w liczbach
naturalnych ma sens. Wyliczmy x.
44 + 13y 2 - y
x = = 6 + 2y +
7 7
Skoro x ma być liczbą naturalną, to
2 - y
= t,
7
gdzie t jest liczbą całkowitą.
Stąd musi być x = 10  13 t, y = 2  7 t, x > 0 i y > 0.
Rozwiązując układ nierówności
10  13 t > 0,
2  7 t > 0,
otrzymujemy rozwiÄ…zania:
x = 10  13 t,
y = 2  7 t,
gdzie t jest liczbą całkowitą niedodatnią.
8. Rozwiązać w liczbach całkowitych równanie
x2 - y2 = 4.
RozwiÄ…zanie
Równanie można zapisać w postaci równoważnej
(x - y) (x + y) = 4.
Iloczyn dwóch liczb całkowitych jest równy 4: gdy obie są równe 2 lub obie są równe -2 lub
jedna z nich jest równa 4, a druga 1 lub jedna jest równa -4, a druga -1.
Zatem mamy 6 przypadków
1) x  y = 2 i x + y = 2, skÄ…d 2x = 4, zatem x = 2, a y = 0,
2) x  y = -2 i x + y = -2, skÄ…d 2x = -4, zatem x = -2, a y = 0,
3) x  y = 4 i x + y = 1, skąd 2x = 5, zatem x nie jest liczba całkowitą i takie rozwiązanie
nas nie interesuje,
Pozostałe przypadki również nie dają rozwiązań.
W rezultacie rozwiązania wyglądają następująco: x = 2, y = 0 oraz x = -2, y = 0.
9. KorzystajÄ…c ze wzoru
a Å" b
[a,b] = .
(a,b)
Znalez
ć najmniejszą wspólną wielokrotność liczb 279 i 372.
RozwiÄ…zanie.
Zastosujmy algorytm Euklidesa w celu znalezienia największego wspólnego dzielnika
liczb 372 i 279.
372 = 1 Å" 279 + 93
279 = 3 Å" 93.
Zatem
372 Å" 279 103788
[372, 279] = = = 1116.
(372, 279) 93
10. Największy wspólny dzielnik liczb a i b jest równy 24, a ich najmniejsza wspólna
wielokrotność jest równa 2496. Znalez
ć liczby a i b.
RozwiÄ…zanie.
IstniejÄ… liczby caÅ‚kowite m i n Takie, że a = 24 Å" m, b = 24 Å" n, (m, n) = 1.
Możemy przyjąć, że m < n. ponieważ 2496 jest najmniejszą wspólna wielokrotnością liczb
a i b, to
24m Å" 24n
2496 = .
24
 StÄ…d
m Å" n = 104 = 8 Å" 13.
Ponieważ (m, n) = 1, to m Å" n = 1 Å" 104 lub m Å" n = 8 Å" 13.
a) JeÅ›li m = 1, n = 104, to a = 24 Å" 1 = 24, b = 24 Å" 104 = 2496,
b) JeÅ›li m = 8, n = 13, to a = 24 Å" 13 = 192, b = 24 Å" 13 = 312.
11. Pokazać, że
(a, b) (a, c) (b, c) [a, b] [a, c] [b, c] = a2 b2 c2,
a, b, c są dowolnymi liczbami całkowitymi.
RozwiÄ…zanie.
Wystarczy skorzystać ze wzoru podanego w przykładzie 17 oraz z faktu, że mnożenie liczb
całkowitych jest działaniem przemiennym i łącznym.
12. Znalez
ć wszystkie liczby całkowite, które przy dzieleniu przez 5 dają resztę 3, a przy
dzieleniu przez 6 dajÄ… resztÄ™ 5. Jakie reszty dajÄ… te liczby przy dzieleniu przez 60.
RozwiÄ…zanie
Oznaczmy szukane liczby symbolem x. Zgodnie z warunkami zadania x = 5s+3 i x =
6t+5, gdzie s,t są dowolnymi liczbami całkowitymi. Z powyższych zależności wynika, że 5s 
6t = 2. Otrzymaliśmy równanie nieoznaczone, którego rozwiązanie ma postać: s = 4 + 6k, t =
3+6t, gdzie k jest dowolną liczbą całkowitą. W takim razie x = 5(4 + 6k) + 3 = 23 + 30k.
Jeśli k = 2u, to x = 23 + 60u. Jeśli k = 2u +1, to x = 23 + 30 + 60u = 53 + 60u, gdzie u jest
dowolną liczbą całkowitą. Zatem poszukiwane liczby całkowite przydzieleniu przez 60 dają
reszty 23 albo 53.
II. Liczby pierwsze, liczby złożone, liczby względnie pierwsze
1. Pokazać, że liczbę 5050505 nie można przedstawić w postaci sumy dwóch liczb
pierwszych.
RozwiÄ…zanie
W przypadku, gdy 5050505 = 2+5050503, liczba 50505053 jest liczbÄ… podzielnÄ… przez 9, a
więc nie jest liczbą pierwszą. Wszystkie liczby pierwsze oprócz 2 są liczbami nieparzystymi,
a suma liczb nieparzystych jest liczba parzystą. Zatem nie można liczby 5050505 przedstawić
w postaci sumy dwóch liczb pierwszych.
2. Niech c = a2 + 4b4, gdzie a,b są liczbami naturalnymi różnymi od 1. Pokazać, że wtedy c
jest liczbą złożoną.
RozwiÄ…zanie
Zauważmy, że c = a4 + 4a2 b2 + 4b2 - 4a2 b2 = (a2 + 2 b2)2 - 4a2 b2 = (a2 + 2 b2  2ab) (a2 + 2
b2 + 2ab). Jeśli a = b = 1, to c = 5, a więc nie jest liczbą pierwszą
3. Podać przykład takich czterech liczb naturalnych a, b, c, d dla których nie ma żadnej
liczby naturalnej n, przy której liczby a + n, b + n, c + n, d + n byłyby parami względnie
pierwsze.
RozwiÄ…zanie.
Takimi liczbami są na przykład a = 1, b = 2, c = 3, d = 4, bo jeśli n jest dowolną liczbą
całkowitą, to
a + n , c + n - dla n nieparzystego są parzyste, a więc nie są względnie pierwsze.
b + n , d + n - dla n parzystych są parzyste, a więc nie są względnie pierwsze.
4. Pokazać, że dla liczb naturalnych n, liczba n33 + 8 jest liczba złożoną.
RozwiÄ…zanie.
Ponieważ
n33 + 8 = n3"11 + 23 = (n11 + 2 ) (n22 - 2 n11 + 4),
więc n33 + 8 , jako iloczyn dwóch liczb naturalnych jest liczbą złożoną.
5. Znalez
ć liczbę pierwszą p , jeśli wiadomo, że 4p2 + 1 i 6p2 + 1 są liczbami pierwszymi.
RozwiÄ…zanie.
Wszystkie liczby naturalne większe od 2 można przedstawić w postaci
5 n, 5 n Ä… 1, 5 n Ä… 2,
gdzie n jest dowolna liczba naturalnÄ….
Liczby postaci 5 n są pierwsze tylko dla n = 1. Jeśli p = 5, to 4 p2 + 1 = 101, 6 p2 + 1 =
151. Jak widać, znalez
liśmy liczbę pierwszą spełniającą warunki zadania. Wykażemy teraz,
że nie istnieją inne liczby pierwsze te warunki spełniające. Rzeczywiście, jeśli p = 5 n ą 1,
to
4 p2 + 1 = 5 (20 n2 ą 8 n + 1), a więc jest liczbą złożoną,
jeśli p = 5 n ą 2, to
6 p2 + 1 = 5 (30 n2 ą 24 n +1) i też jest liczba złożoną.
6. Niech a i b będą liczbami naturalnymi. Udowodnić, że jeżeli 40 a = 51 b, to a + b jest
liczba złożoną.
RozwiÄ…zanie
Zauważmy, że a + b = 13 (4b  3a).
III. Kongruencje
1. Czy
51984 a" 1983 (mod 25)
RozwiÄ…zanie.
Liczba 51984 nie przystaje do liczby 1983 modulo 25 , gdyż liczba 25 nie dzieli liczby
1983.
2. Wykazać, że
25n+ 1 + 45n+ 1 - 6 a" 0 (mod31).
RozwiÄ…zanie.
Zauważmy, że
25 a" 1(mod31), 25n+ 1 a" 2 (mod31),
45 a" 1(mod31), 45n+ 1 a" 4 (mod31).
Zatem
25n+ 1 + 45n+ 1 a" 6 (mod31).
Co jest równoważne temu, że
25n+ 1 + 45n+ 1 - 6 a" 0 (mod31).
3. Jaka jest cyfra jedności liczby 21000 ?
RozwiÄ…zanie.
Zauważmy, że
25 a" 2 (mod10), 210 a" 22 (mod10), 250 a" 210 (mod10).
Z przechodniości kongruencji dostajemy
250 a" 22 (mod10).
Otrzymaną kongruencję podnieśmy stronami do potęgi 5. Wówczas
2250 a" 210 (mod10).
Powtórnie korzystając z przechodniości rozważanej relacji, otrzymujemy
2250 a" 22 (mod10).
Podnosząc powyższą kongruencję stronami do potęgi 4, dostajemy
21000 a" 256 (mod10).
Z kolei 256 a" 6 (mod 10). Zatem
21000 a" 6 (mod10).
Z otrzymanej równości wynika, że cyfra jedności liczby 21000 jest równa 6.
4. Niech p będzie liczbą pierwszą. Liczby a i b niech będą liczbami całkowitymi takimi,
że
a2 a" b2 (mod p). Wtedy p dzieli a + b lub p dzieli a  b.
RozwiÄ…zanie.
Jeśli a2 a" b2 (mod p), a2  b2 a" (mod p). ze wzorów uproszczonego mnożenia i definicji
relacji przystawania modulo p wynika, że liczba pierwsza p dzieli iloczyn (a  b) (a + b).
Zatem liczba pierwsza p dzieli a  b lub a + b.
5. Wykazać, że liczba naturalna A dzieli się przez 11 wtedy i tylko wtedy gdy różnica
pomiędzy sumą jej cyfr znajdujących się na miejscach parzystych i suma jej cyfr
znajdujÄ…cych siÄ™ na miejscach nieparzystych dzieli siÄ™ przez 11.
RozwiÄ…zanie.
Niech kolejnymi cyframi liczby A w układzie dziesiętnym będą a , a , . . . , a .
1 2 n
Wówczas
A = a 10n  1 + a 10n  2 + . . . +a 10 + a .
1 2 n  1 n
Rozważmy wielomian
f(x) = a xn  1 + a xn  2 + . . . +a x + a
1 2 n  1 n.
Oczywiście, A = f(10). Stąd wobec kongruencji 10 a" -1 (mod 11), otrzymujemy
f(10) a" -1 (mod 11). StÄ…d
a + a  a + . . . a" A (mod 11).
1 2 3
6. Wyznaczyć wszystkie pierwiastki kongruencji
x3  2x + 1 a" (mod 5).
RozwiÄ…zanie.
Nasza kongruencja może mieć co najwyżej 5 pierwiastków. Aby je wszystkie znalez
ć
wystarczy sprawdzić które spośród liczb zbioru { 0, 1, 2, 3, 4 } są pierwiastkami naszej
kongruencji. Liczby 0, 3, 4 pierwiastkami naszej kongruencji nie sÄ…. Natomiast liczby 1,
2 spełniają kongruencję.
Wszystkie rozwiązania naszej kongruencji w liczbach całkowitych mają postać
x = 1 + 5t, x = 2 + 5t,
gdzie t jest dowolna liczbą całkowitą.
7. Rozwiązać kongruencję
x2 - x + 1 a" 0 (mod 2).
RozwiÄ…zanie.
Kongruencja nie jest spełniona, gdyż x (x  1) + 1 jest liczba nieparzystą, a więc
niepodzielnÄ… przez 2.
8. Rozwiązać kongruencję
x (x + 1) (x + 2) (x + 3) a" (mod 24).
RozwiÄ…zanie.
Kongruencja jest tożsamościowa, gdyż x, x + 1, x + 2, x + 3 są to kolejne cztery liczby
naturalne.
9. Wyznaczyć resztę z dzielenia liczby
1994 " 1995 " 1996 + 19972 przez 7.
RozwiÄ…zanie.
Zauważmy, że 1995 = 285 " 7. Dalej 1997 a" 2(mod 7), a więc 19972 a" 4(mod 7). Z
powyższego wynika, że reszta przy dzieleniu naszej liczby przez 7 wynosi 4.
10. Pokazać, że 211" 31 a" 2 (mod 11 " 33).
RozwiÄ…zanie
31 " 11 = 341, 11 " 33  1 = 340 = 5 " 68, 25 a" -1 (mod 11), stÄ…d
211" 31-1 a"1 (mod 11) (a).
Z kolei 25 a" 1 (mod 31). Zatem
211" 31-1a"1 (mod 31) (b).
Z równości (a) i (b) oraz z własności kongruencji wynika, że
211" 31-1 a" 1 (mod 11" 31).
11. Policzyć 1643(mod 25).
RozwiÄ…zanie.
Z twierdzenia Eulera wynika, że 1620a"1(mod25). Z własności kongruencji mamy
1640a"1(mod25). Ponieważ 163a"21(mod25), to 1643a"21(mod25).
12. Czy istnieje liczba całkowita x spełniająca układ równań
xa"3(mod5),
xa"6(mod8) ,
xa"2(mod7),
xa"3(mod11)?
RozwiÄ…zanie.
Liczby 5, 8, 7, 11 są parami względnie pierwsze. Zatem na mocy chińskiego twierdzenia o
resztach taka liczba x istnieje.
Funkcja Eulera Ć(x)
1. Policzyć: Ć(55), Ć(125), Ć(375).
RozwiÄ…zanie.
Policzmy Ć(55).
55 = 5 · 11. Ponieważ i 5 i 11 sÄ… różnymi liczbami pierwszymi, zatem na mocy wÅ‚asnoÅ›ci
funkcji Eulera, otrzymujemy Ć(55) = 4 · 10 = 40.
Policzmy Ć(125).
125 = 53. Zatem Ć(125) = 52 · 4 = 100.
Policzmy Ć(375).
1 1
375 = 3 ·53 . Zatem Ć(375) = 3 ·53 (1 - ) (1 - ) = 200.
3 5
2. Znalez
ć liczbÄ™ naturalnÄ… a, jeÅ›li Ć(a )= 3600 oraz a = 3Ä…· 5² · 7Å‚.
RozwiÄ…zanie.
a = 3Ä…· 5² · 7Å‚, zatem Ć(a) = 3Ä… - 1· 2 · 5² - 1 · 4 · 7Å‚ - 1 · 6 = 24 · 3Ä…· 5² - 1 · 7Å‚ - 1. Ale
3600 = 24 · 32· 52 · 70, wiÄ™c 24 · 3Ä…· 5² - 1 · 7Å‚ - 1 = 24 · 32· 52 · 70. StÄ…d Ä… = 2, ² = 3, Å‚ = 1 i
w konsekwencji a = 32· 53 · 7 = 7875.
3. Znalez
ć liczbÄ™ naturalnÄ… a jeÅ›li, Ć(a) = 40, a = p · q, gdzie p, q sÄ… różnymi liczbami
pierwszymi, oraz p  q = 6.
RozwiÄ…zanie.
Z warunków zadania wynika, że Ć(a) = Ć(p · q) = (p - 1) (q  1) = 40. Otrzymujemy
zatem układ równań
(p - 1) (q  1) = 40,
p  q = 6.
Rozwiązując ten układ otrzymujemy p = 11, q = 5. Szukaną liczbą jest więc 55.
4. Rozwiązać równanie Ć(x) = 2"3-1 x, gdzie x jest liczba naturalną.
RozwiÄ…zanie.
Funkcja Eulera przyjmuje wartości w zbiorze liczb naturalnych, x jest liczbą podzielną
przez 3. Zatem x ma postać x = 3a " k, gdzie liczby a i k są liczbami naturalnymi oraz
(3, k) = 1. Z własności funkcji Eulera wynika, że
Ć(3a " k) = 2 " 3a-1 " Ć(k). Więc z warunku zadania mamy 2 "3a-1 " Ć(k) = 2 " 3-1 " 3a " k.
Skąd wynika, że Ć(k) = k. Ponieważ tylko liczba 1 spełnia równość Ć(k) = k, więc x = 3a ,
gdzie a jest dowolnÄ… liczbÄ… naturalnÄ….