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