Elementy teorii liczb w przykladach, Politechnika Łódzka


I. Podzielność liczb całkowitych

1. Liczba a = 42157 przy dzieleniu przez pewną liczbę dodatnią całkowitą b daje iloraz k = 231 i resztę r. Znaleźć dziennik b oraz resztę r.

Rozwiązanie.

0x08 graphic
a = 42157 = 231 b + r, 0 < r < b. Stąd

więc b = 182, r = 115.

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

0x08 graphic
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,

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. Znaleźć 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. Znaleźć sumę n wyrazów ciągu Sn= 1 + 11 + 111 + ... + 11...1 (Sn jest sumą n składników).

Rozwiązanie.

0x08 graphic
0x08 graphic
Sn = 1 + 11 + 111 + ... + 11..1 =

6. Znaleźć 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 k1 + 1

(4q + 3)2 = 8 (2q2 + 3q + 1) + 1 = 8 k2 + 1,

gdzie k1 = 2q2 + q, a k2 = 2q2 + 3q + 1.

9. Dowieść, że dla naturalnych n, n2 dzieli (n + 1)n - 1.

Rozwiązanie.

0x08 graphic
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 znaleźć 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. Znaleźć parę liczb całkowitych (xo, yo) spełniających związek

42823 xo + 6409 yo = 17.

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 xo i yo istnieją. Wykorzystajmy algorytm Euklidesa do znalezienia liczb xo, yo. Liczmy kolejno

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 xo= - 22, yo=147.

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 (xo, yo), to wszystkie rozwiązania dane są wzorami

x = xo+ b1 t , y = yo- a1 t,

0x08 graphic
0x08 graphic
gdzie

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 xo= -88, yo= 588.

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.

0x08 graphic
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:

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.

0x08 graphic
Liczby 17 oraz 39 są względnie pierwsze, zatem nasze równanie posiada rozwiązanie w liczbach całkowitych. Wyliczmy x:

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.

0x08 graphic
Liczby 7 i 13 są względnie pierwsze, zatem poszukiwanie rozwiązań w liczbach naturalnych ma sens. Wyliczmy x.

Skoro x ma być liczbą naturalną, to

0x08 graphic
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

0x08 graphic
Znaleźć 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

0x08 graphic

10. Największy wspólny dzielnik liczb a i b jest równy 24, a ich najmniejsza wspólna wielokrotność jest równa 2496. Znaleźć liczby a i b.

Rozwiązanie.

Istnieją liczby całkowite m i n Takie, że a = 24 ⋅ m, b = 24 ⋅ n, (m, n) = 1.

0x08 graphic
Możemy przyjąć, że m < n. ponieważ 2496 jest najmniejszą wspólna wielokrotnością liczb a i b, to

0x08 graphic

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. Znaleźć 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.

0x08 graphic

Ułamki łańcuchowe

0x08 graphic
1. Rozwinąć ułamek

na ułamek łańcuchowy.

Rozwiązanie.

Zastosujmy algorytm Euklidesa do liczb 44 i 13

44 = 3 ⋅ 13 + 5

13 = 2 ⋅ 5 + 3

5 = 1 ⋅ 3 + 2

3 = 1 ⋅ 2 + 1

2 = 2 ⋅ 1.

Stąd

0x08 graphic

2. Rozwinąć na ułamek łańcuchowy ułamek

0x08 graphic
Liczby a i b są naturalne.

Rozwiązanie.

Zastosujmy algorytm Euklidesa

6a4 + 12a3 + 13a2 + 10a + 4 = a ⋅ (6a3 + 12a2 + 7a + 1) + 6a2 + 9a + 4

6a3 + 12a2 + 7a + 1 = a ⋅ (6a2 + 9a + 4) + 3a2 + 3a + 1

6a2 + 9a + 4 = 2 ⋅ (3a2 + 3a + 1) + 3a + 2

3a2 + 3a + 1 = a ⋅ (3a + 2) + a + 1

3a + 2 = 2 ⋅ (a + 1) + a

a + 1 = 1 ⋅ a + 1

a = a ⋅ 1

poszukiwany ułamek łańcuchowy ma postać:

0x08 graphic

3. Zamienić na ułamek zwyczajny ułamek łańcuchowy

0x08 graphic
Liczba x jest liczbą naturalną.

Rozwiązanie.

0x08 graphic
Policzmy

0x08 graphic

Zatem poszukiwanym ułamkiem zwykłym jest wyrażenie:

0x08 graphic

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. Znaleźć 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ć, znaleź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

0x08 graphic

Rozwiązanie.

Liczba 51984 nie przystaje do liczby 1983 modulo 25 , gdyż liczba 25 nie dzieli liczby 1983.

0x08 graphic
2. Wykazać, że

Rozwiązanie.

0x08 graphic
Zauważmy, że

Zatem

0x08 graphic

Co jest równoważne temu, że

0x08 graphic

3. Jaka jest cyfra jedności liczby 21000 ?

Rozwiązanie.

Zauważmy, że

0x08 graphic

0x08 graphic
Z przechodniości kongruencji dostajemy

Otrzymaną kongruencję podnieśmy stronami do potęgi 5. Wówczas

0x08 graphic

Powtórnie korzystając z przechodniości rozważanej relacji, otrzymujemy

0x08 graphic

Podnosząc powyższą kongruencję stronami do potęgi 4, dostajemy

0x08 graphic

Z kolei 256 Ⴚ 6 (mod 10). Zatem

0x08 graphic

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 Ⴚ b2 (mod p). Wtedy p dzieli a + b lub p dzieli a - b.

Rozwiązanie.

Jeśli a2 Ⴚ b2 (mod p), a2 - b2 Ⴚ (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ą a1, a2, . . . , an.

Wówczas

A = a1 10n - 1 + a2 10n - 2 + . . . +an - 1 10 + an .

Rozważmy wielomian

f = a1 xn - 1 + a2 xn - 2 + . . . +an - 1 x + an.

Oczywiście, A = f(10). Stąd wobec kongruencji 10 Ⴚ -1 (mod 11), otrzymujemy f(10) Ⴚ -1 (mod 11). Stąd

a1 + a2 - a3 + . . . Ⴚ A (mod 11).

6. Wyznaczyć wszystkie pierwiastki kongruencji

x3 - 2x + 1 Ⴚ (mod 5).

Rozwiązanie.

Nasza kongruencja może mieć co najwyżej 5 pierwiastków. Aby je wszystkie znaleźć 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ą.

0x08 graphic

7. Rozwiązać kongruencję

x2 - x + 1 Ⴚ 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) Ⴚ (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 ≡ 2(mod 7), a więc 19972 ≡ 4(mod 7). Z powyższego wynika, że reszta przy dzieleniu naszej liczby przez 7 wynosi 4.

10. Pokazać, że 211∙ 31 ≡ 2 (mod 11 ∙ 33).

Rozwiązanie

31 ∙ 11 = 341, 11 ∙ 33 - 1 = 340 = 5 ∙ 68, 25 ≡ -1 (mod 11), stąd

211∙ 31-1 = 1 (mod 11) (a).

Z kolei 25 ≡ 1 (mod 31). Zatem

211∙ 31-1 = 1 (mod 31) (b).

Z równości (a) i (b) oraz z własności kongruencji wynika, że

211∙ 31-1 = 1 (mod 11∙ 31).

  1. Policzyć 1643(mod 25).

Rozwiązanie.

Z twierdzenia Eulera wynika, że 1620≡1(mod25). Z własności kongruencji mamy 1640≡1(mod25). Ponieważ 163≡21(mod25), to 1643≡21(mod25).

  1. Czy istnieje liczba całkowita x spełniająca układ równań

x≡3(mod5),

x≡6(mod8) ,

x≡2(mod7),

x≡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).

375 = 3 ·53 . Zatem φ(375) = 3 ·53 (1 - 0x01 graphic
) (1 - 0x01 graphic
) = 200.

  1. Znaleźć 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.

  1. Znaleźć 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.

  1. 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ą.

16

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic



Wyszukiwarka

Podobne podstrony:
Elementy teorii liczb w zadaniach, Politechnika Łódzka
Elementy teorii liczb w przykładach
md elementy teorii liczb
Elementy teorii liczb w zadaniach
md elementy teorii liczb
Przykładowa analiza AWZ, politechnika łódzka, inżynieria chemiczna i procesowa, rok I semestr 1, bez
algebra zaliczenie przyklad, Studia, Politechnika Łódzka - Pendrive, Algebra
Egzamin przyklad, BIOTECHNOLOGIA POLITECHNIKA ŁÓDZKA, CHEMIA FIZYCZNA, chemia fizyczna
sprawko Malczewski, Politechnika Łódzka Elektrotechnika, magisterskie, 1 sem, systemy el-en, Systemy
Tabelka pomiarowa do 21, BIOTECHNOLOGIA POLITECHNIKA ŁÓDZKA, CHEMIA FIZYCZNA
1.10spis treci do cigi z metro, POLITECHNIKA (Łódzka), Metrologia, 1semestr
Prawo inżynierskie i ochrona własności intelektualnych. Wykład 3, Studia, Politechnika Łódzka - Pend
obliczenia i wnioski, BIOTECHNOLOGIA POLITECHNIKA ŁÓDZKA, CHEMIA FIZYCZNA

więcej podobnych podstron