Metoda kongruencji w uzasadnianiu podzielności liczb

Metoda kongruencji w uzasadnianiu podzielności liczb

Zbigniew Stebel

Lipiec 2016

1. Pojęcie podzielności.

Liczba a jest podzielna przez niezerową liczbę, b wtedy, gdy istnieje liczba całkowita, k taka,
że

𝑎 = 𝑘 ∙ 𝑏

Fakt, że liczba a jest podzielna przez b notujemy w postaci: 𝑎 ⋮ 𝑏. Mówimy również, że liczba
b jest dzielnikiem liczby a.

Fakt 1.

Jeśli liczba a jest podzielna przez b i liczba b jest podzielna przez a to wówczas liczby a i b są
równe.

Dowód

𝑎 ⋮ 𝑏 ∧ 𝑏 ⋮ 𝑎 ⇒ 𝑎 = 𝑏

𝑎 = 𝑏 ∙ 𝑘1 ∧ 𝑏 = 𝑎 ∙ 𝑘2 ⇒ 𝑎 = 𝑎 ∙ 𝑘2 ∙ 𝑘1,

czyli 𝑘1 ∙ 𝑘2 = 1, stąd 𝑘1 = 𝑘2 = 1 lub 𝑘1 = 𝑘2 = −1 ∎

Dla dzielenia liczb całkowitych a i b bez reszty zachodzi 𝑎 ⋮ 𝑏 ⇒ 𝑎 = 𝑏 ∙ 𝑘.

Dla dzielenia liczb całkowitych a i b z resztą r zachodzi 𝑎 = 𝑏 ∙ 𝑞 + 𝑟, 0 ≤ 𝑟 < 𝑏.

2. Pojęcie kongruencji.

Liczby a i b są kongruentne wtedy, gdy mają takie same reszty przy dzieleniu przez liczbę
całkowitą i dodatnią m. Mówimy wówczas, że liczby a i b przystają modulo m.

Fakt, że liczba a ma taką samą resztę jak liczba b przy dzieleniu przez liczbę m zapisujemy w
postaci 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚).

Fakt 2.

Jeśli liczby a i b są kongruentne modulo m to różnica tych liczb jest podzielna przez liczbę m.

Symbolicznie 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) ⇒ 𝑎 − 𝑏 ⋮ 𝑚.

Dowód

Załóżmy, że 𝑎 = 𝑚 ∙ 𝑞1 + 𝑟, 𝑏 = 𝑚 ∙ 𝑞2 + 𝑟, gdyż liczby a i b mają takie same reszty.

Wówczas 𝑎 − 𝑏 = 𝑚 ∙ (𝑞1 − 𝑞2) = 𝑚 ∙ 𝑞 ≡ 0 (𝑚𝑜𝑑 𝑚)∎

Przykłady

24 ≡ 4 (𝑚𝑜𝑑 5) ↔ 24 − 4 ⋮ 5

24 ≡ 0 (𝑚𝑜𝑑 8) ↔ 24 − 0 ⋮ 8

2016 ≡ 6 (𝑚𝑜𝑑 10) ↔ 2016 − 6 ⋮ 10

Pewne własności kongruencji.

Załóżmy, że 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛), 𝑐 ≡ 𝑑 (𝑚𝑜𝑑 𝑛). Wówczas zachodzą następujące własności:

1. 𝑎 + 𝑐 ≡ 𝑏 + 𝑑 (𝑚𝑜𝑑 𝑛)
2. 𝑎 − 𝑐 ≡ 𝑏 − 𝑑 (𝑚𝑜𝑑 𝑛)
3. 𝑎 ∙ 𝑐 ≡ 𝑏 ∙ 𝑑 (𝑚𝑜𝑑 𝑛)
4. 𝑎𝑚 ≡ 𝑏𝑚 (𝑚𝑜𝑑 𝑛)
3. Metoda kongruencji w zadaniach.

Zadanie 1.

Uzasadnimy, że 7𝑛 − 1 ⋮ 6.

7 ≡ 1 (𝑚𝑜𝑑 6)

Z własności (4) 7𝑛 ≡ 1𝑛 = 1 (𝑚𝑜𝑑 6) → 7𝑛 − 1 ≡ 0(𝑚𝑜𝑑 6)∎

Uzasadnimy, że 13𝑛 + 3𝑛+2 ⋮ 10.

13 ≡ 3 (𝑚𝑜𝑑 10) → 13𝑛 ≡ 3𝑛(𝑚𝑜𝑑 10) z własności 4.

13𝑛 + 3𝑛+2 = 3𝑛 + 3𝑛 ∙ 32 = 3𝑛(1 + 9) = 10 ∙ 3𝑛 ≡ 0 (𝑚𝑜𝑑 10)∎

Zadanie 2.

Uzasadnimy, że 5𝑛 + 11𝑛 + 2 ⋮ 6.

51 ≡ −1 (𝑚𝑜𝑑 6) → 5𝑛 ≡ (−1)𝑛 (𝑚𝑜𝑑 6), oraz

111 ...