Zadania

I. Podzielność liczb całkowitych

1. Pewna liczba sześciocyfrowa a kończy się cyfrą 5. Jeśli tę cyfrę przestawimy na miejsce pierwsze ze strony lewej, to otrzymamy nową liczbę cztery razy większą od poprzedniej. Znaleźć liczbę a

2. Znaleźć liczbę czterocyfrową n² będącą kwadratem pewnej liczby naturalnej n, której cyfra tysięcy jest równa cyfrze dziesiątek, a cyfra setek jest o 1 większa od cyfry jedności

3. Znaleźć sumę n wyrazów ciągu S_n = 2 + 22 + 222 + ... + 222...2 ( S_n jest sumą n składników).

4^*. Dowieźć, że dla naturalnych n liczba ( n + 1 )ⁿ - 1 jest podzielna przez liczbę n² .

5^*. Pokazać, że dla dowolnej liczby naturalnej n iloczyn ( n + 1 ) ( n + 2 ) ... ( n + n ) dzieli się przez 2ⁿ.

6^*. Pokazać, że dla dowolnych liczb naturalnych liczb m i n, iloczyn m⋅n ( m⁴ - n⁴ ) jest podzielny przez 30.

Wskazówka:

Wykazać, że liczba 30 dzieli liczbę m⁵ - m.

7. Niech będą dane liczby całkowite a, b, c, d, n spełniające warunki:

liczba n dzieli liczbę ad - bc, liczba n dzieli liczbę a - b, liczby b i n są względnie pierwsze ( to znaczy, że nie mają wspólnych dzielników różnych od 1 ). Pokazać, że liczba

c - d jest podzielna przez n.

10. Pokazać, że jeśli licznik ułamka jest różnicą kwadratów dwóch liczb nieparzystych. a mianownik jest sumą kwadratów tych liczb, to taki ułamek można skrócić przez 2, a nie można skrócić przez 4.

11^*. Znaleźć wszystkie liczby naturalne n, dla których liczba n² + 1 jest podzielna przez n.

12. Znaleźć wszystkie liczby całkowite x ≠ 3 takie, że liczba x - 3 dzieli liczbę x³ - 3.

13. Wykazać, że dla dowolnej liczby całkowitej a, największy wspólny dzielnik, (a, a + 2) jest równy 1 lub 2.

14. Udowodnić, że jeśli n jest liczbą całkowitą, to iloczyn n (n + 1) (n + 2) (n + 3) (n + 4)

dzieli się bez reszty przez liczbę 120.

15. Pokazać, że dla dowolnej liczby naturalnej n liczba ( n² + 2 ) nie jest podzielna przez 4.

16*^*. ( Zadanie konkursowe z zawodów stopnia drugiego LIV Olimpiady Matematycznej)

Dowieść, że istnieje taka liczba całkowita n > 2003, że w ciągu

każdy wyraz jest dzielnikiem wszystkich wyrazów po nim następujących.

Algorytm Euklidesa, największy wspólny dzielnik, najmniejsza wspólna wielokrotność

17. Stosując algorytm Euklidesa znaleźć największy wspólny dzielnik liczb:

a) 963 i 657, b) 423 i 198,

c) 2947 i 3997, d) 1109 i 4999,

e) 7469 i 2464, f) 2689 i 4001,

g) 42823 i 6409, h) 5033464705 i 3137640337.

18^*. Pokazać, że jeśli a = c k + r, b = c k₁ + r₁, gdzie a, b, k, k₁, r, r₁ są liczbami całkowitymi nieujemnymi, a liczba c jest liczbą dodatnią, to

(a, b, c) = (c, r, r₁).

Sformułować wynikające z powyższego twierdzenie o znajdowaniu (a, b, c). Uogólnić na przypadek n liczb.

19. Korzystając z zadania 18, znaleźć największe wspólne dzielniki następujących liczb:

1. 229, 391, 667,

2. 588, 2058, 2849,

3. 31605, 13524, 12915, 11067,

4. 279, 372, 1395,

5. 2737, 9163, 9639,

6. 2988, 3735, 8134, 14525.

20. Stosując rozkład na czynniki pierwsze, znaleźć najmniejsze wspólne wielokrotności następujących liczb

1. 360, 504, b) 2520, 6600,

c) 187, 533, d) 9163, 2737, 9639,

5. 374, 1599, 9061.

21. Znaleźć najmniejszą wspólną wielokrotność następujących liczb

a) 252 i 468, b) 279 i 372,

b) 178 i 881, d) 318 i 477.

22. Największy wspólny dzielnik liczb naturalnych jest równy 24, a największa wspólna wielokrotność tych liczb jest równa 2496. Znaleźć te liczby.

23, Pokazać, że dla liczb całkowitych a, b, c

(a, b) (a, c) (b, c) [a, b] [a, c] [b, c] = a² b² c².

24. Pokazać, że dla liczb całkowitych a, b, c

Równania nieoznaczone

25. Znaleźć największy wspólny dzielnik liczb 1819 i 3587 oraz znaleźć liczby x i y spełniające związek

1819 x + 3587 y = 17.

26. Udowodnić, że nie istnieją liczby całkowite x, y spełniające związki x + y = 100 oraz (x, y) = 3.

27. Znaleźć wszystkie pary liczb naturalnych x, y spełniających związki x + y = 100 oraz (x, y) = 5.

28. Rozwiązać w liczbach całkowitych następujące równania

a) 5 x + 4 y = 21 , b) 17 x + 13 y = 181,

c) 5 x - 2 y = -1, d) 6 x + 7 y = 59,

e) 10 x + 7 y = 97, f) 11 x - 8 y = 57.

29. Rozwiązać w liczbach całkowitych następujące równania stosując algorytm Euklidesa

a ) 4 x + 9 y = 91, b) 19 x + 23 y = 3,

c) 11 x + 16 y = 268, d) 47 x - 25 y = 279,

e) 42823 x - 6409 y = 34, f) 963 x + 657 y = 243.

30. Rozwiązać w liczbach naturalnych następujące równania

a) 24 x = 15 y = 9, b) 48 x - 36 y = 15,

c) 126 x - 102 y = 18, d) 423 x + 198 y = 9.

31. Rozwiązać w liczbach naturalnych następujące równanie stosując algorytm Euklidesa

a) 13 x + 25 y = 265, b) 89 x + 13 y = 8965.

32. Liczbę 1000 rozłożyć na takie dwa składniki dodatnie, aby pierwszy był wielokrotnością 10, a drugi w dzieleniu przez 13 dawał resztę 3
.

33. Jakie liczby całkowite należy podstawić zamiast x, y, z w ułamkach

aby pierwszy z nich stał się liczbą całkowita, drugi liczbą całkowitą parzystą, trzeci liczbą całkowita nieparzystą?

Ciąg liczb naturalnych, którego dwa pierwsze wyrazy są dane, a następne są określone wzorem rekurencyjnym a_n = a_n-1 + a _n-2 (n ≥ 3), nazywamy ciągiem Fibonacciego, od nazwiska słynnego matematyka włoskiego XIII stulecia.

34^*. Dziesiąty wyraz ciągu Fibonacciego wynosi 369. Znaleźć pozostałe wyrazy.

35. Rozwiązać w liczbach całkowitych układ równań

2 x + 3 y - 4 z = 18,

3 x + 8 y + z = 2.

36. Rozwiązać w liczbach naturalnych układ równań

2 x - 3 y + 2 z = 23,

3 x - 2 y + z = 5.

37. Rozwiązać w liczbach naturalnych układ równań

5 x + 7 y + 6 z = 593,

11 x + 10 y + 4 z = 455.

38. Rozwiązać w liczbach naturalnych układ równań

7 x + 10 y - 13 z - 2u = 113,

5 x - 3 y + 2 z - 3 u = 36,

3 x - 2 y - 3 z + 4 u = 35.

40. Rozwiązać w liczbach całkowitych równanie

a) 5 x + 2 y - z = 6, b) 7x + 3 y + 5z = 22.

c) 7 x + 15 y - 22 z = 29, d) 8 x + 11 y - 19 z = 62.

41. Znaleźć liczby całkowite, które przy dzieleniu:

1. przez 12 dają resztę 0, przez 11 dają resztę 8,

2. przez 15 dają resztę 0, przez 8 dają resztę 1 i przez 11 dają resztę 6.

Odp.:105+1320t, t
Z.

42. Znaleźć ogólną postać liczb całkowitych, które przy dzieleniu przez 5 dają resztę 3, przy dzieleniu przez 6 dają resztę 5. Jaka resztę dają te liczby przy dzieleniu przez 60 oraz przy dzieleniu przez 90.

Ułamki łańcuchowe

43. Zamienić na ułamki zwyczajne następujące ułamki łańcuchowe

gdzie a, b, c, x są liczbami naturalnymi.

44. Rozwinąć na ułamki łańcuchowe następujące ułamki

45. Rozwinąć na ułamek łańcuchowy następujące przybliżenie liczby π - 3,1415926.

II. Liczby pierwsze, liczby względnie pierwsze

46. Udowodnić następujące twierdzenie:

Liczby całkowite a i b takie, że a ≠ 0 lub b ≠ 0 są względnie pierwsze wtedy i tylko wtedy gdy istnieją liczby całkowite x i y takie, że

a x + b y = 1.

47, Pokazać, że jeśli p jest liczbą pierwszą większą od 5, to p² przy dzieleniu przez 30 daje resztę równą 1 lub 19.

48^*. Znaleźć liczbę pierwszą p, jeżeli wiadomo, że 4 p² +1 i 6 p² + 1 są liczbami pierwszymi.

49. Znaleźć taką liczbę naturalną n, że f(n) jest liczbą złożoną,

1. f(n) = n² + n + 17,

2. f(n) = n² + 21 n + 1,

3. f(n) = 3 n² + 3n + 23.

50. Odpowiedz, jakie liczby są pierwsze w następujących zbiorach?

1. { 1, 3, 5, 7, 9},

2. { 2, 4, 6, 8, 10,...}.

51. Znaleźć najmniejszą liczbę złożoną postaci 3ⁿ + 2.

52^*. Pokazać, że spośród liczb postaci 2 p + 1, gdzie p jest liczbą pierwszą, tylko jedna jest sześcianem pewnej liczby tej postaci.

53. Jakie liczby między 2320 i 2350 są pierwsze?

54^*. Dowieść, że przy wszelkim całkowitym k liczby 2 k + 1 i 9 k + 4 są względnie pierwsze, a dla liczb 2 k - 1 i 9 k + 4 znaleźć ich największy wspólny dzielnik w zależności od liczby k.

55^*. Dowieść, że jeżeli a i b są różnymi liczbami całkowitymi, to istnieje nieskończenie wiele liczb naturalnych n takich, że liczby a + n, b + n są liczbami naturalnymi względnie

pierwszymi.

56. Podać przykład takich czterech różnych liczb naturalnych a, b, c, d dla których nie ma żadnej liczby naturalnej n przy której a + n, b + n, c + n, d + n, byłyby parami względnie pierwsze.

57^*. Dowieść, że dla każdej liczby parzystej n > 6 istnieją liczby pierwsze p i q, mniejsze od n - 1 takie, że (n - p, n - q) = 1.

58. Pokazać, że dla n > 1, n - naturalne, liczba n⁴ + 4 jest liczbą złożoną.

59^*. Znaleźć liczbę pierwszą p, jeżeli wiadomo, że 4 p² + 1 i 6 p² + 1 są liczbami pierwszymi.

III. Kongruencje

60. Obliczyć ostatnia cyfrę liczby 2¹⁰⁰⁰.

61. Pokazać, że 61! ≡ 63! (mod 71).

62^*. Wykazać, że liczba A dzieli się przez 11 wtedy i tylko wtedy gdy różnica między sumą jej cyfr znajdujących się na miejscach parzystych i miejscach nieparzystych dzieli się przez 11.

63. Sprawdzić, że przez 11 dzielą się liczby

a) 64640829, b) 2169918747816.

64. Pokazać, że jeśli n jest liczbą nieparzystą, to n² - 1 ≡ 0 (mod 8).

65^*. Pokazać, że jeżeli p jest liczbą pierwszą, to

(a + b)^p = a^p + b^p (mod p).

66^*. Pokazać, że 2^{11 ⋅ 31} ≡ 2 (mod 11 ⋅ 31).

67. Rozwiązać kongruencję

x¹⁰⁰ ≡ 1 (mod 7).

68. Pokazać, że jeśli p jest liczbą pierwszą i a² ≡ b² (mod p), to p dzieli a + b lub p dzieli a - b, gdzie a i b są liczbami całkowitymi.

69. Pokazać, że jeśli f(x) jest wielomianem o współczynnikach całkowitych i f(a) ≡ k (mod m), to f(a + t m) ≡ k (mod m), gdzie k, t są liczbami całkowitymi.

70. Wykazać, że

1. 3⁸⁰ + 7⁸⁰ ≡ 2 (mod 5),

2. 3⁸⁰ + 7⁸⁰ ≡ 2 (mod 100).

.

71. Udowodnić, że jeśli a ≡b (mod m₁) i a ≡ b (mod m₂) i (m₁, m₂) = 1, to a ≡ b mod (m₁ ⋅ m₂).

72. Udowodnić, że jeśli a b ≡c (mod m) i b ≡ d (mod d), to a d ≡c (mod m).

73. Pokazać, że 2 ∙26! ≡ -1(mod29).

74. Rozwiązać kongruencje:

1. 5 x² - 15 x + 22 ≡ 0 (mod 3),

2. x² + 2x + 2 ≡ 0 (mod 5),

3. 3 x ≡ 1 (mod 5),

4. 8 x ≡ 3 (mod 14),

5. x³ - 2 ≡ 0 (mod 2),

6. x² + x + 1 ≡ 0 (mod 2),

7. x (x + 1) (x + 2) ( 9x + 3) ≡ 0 (mod 24),

8. 6 x ≡ 3 (mod 9),

9. 5 x ≡ 3 (mod 12).

IV. Funkcja Eulera. Funkcja π(x).

75. Znaleźć wartości funkcji Eulera dla następujących liczb:

375; 720; 957; 988; 990; 1200; 1440; 1500; 1890; 4320.

76. Znaleźć wartości funkcji Eulera dla liczb pierwszych: 17; 31; 43; 71; 83.

77. Ile jest liczb naturalnych w przedziale [1, 120] które nie są względnie pierwsze z 30?

78. Funkcja Eulera dla argumentu a przyjmuje wartość 120, a = p q, p - q = 2, przy czym p oraz q są dwiema liczbami pierwszymi różnymi między sobą. Znaleźć liczbę a.

79. Funkcja Eulera dla argumentu a przyjmuje wartość 11424, a = p² q² , przy czym p oraz q są dwiema liczbami pierwszymi różnymi między sobą. Znaleźć liczbę a.

80^*. Znaleźć wartość x, jeśli funkcja Eulera w x przyjmuje wartość 12.

81. Znaleźć wartości funkcji π(x) dla następujących argumentów: 4; 7; 10; 12; 25; 37.

82. Rozwiązać kongruencje wykorzystując twierdzenie Eulera:

a) 3x ≡1(mod 5), b) 5x ≡ 6(mod 7), c) 5x ≡ 7(mod 10),

d) 3x ≡8(mod 13), e) 25x ≡ 15(mod 17), f) 25x ≡ 3(mod 12).

---