Dowody podzielności i reszt z dzielenia
W zadaniach z dowodów podzielności i dowodów reszt z dzielenia najczęściej trzeba wykazać, że dane wyrażenie jest podzielne przez określoną liczbę albo ma określoną resztę przy dzieleniu.
W dowodach bardzo często zapisujemy liczby w wygodnej postaci:
- liczby parzyste: 2n
- liczby nieparzyste: 2n + 1
- wielokrotności liczby k: k\cdot n
gdzie n jest liczbą całkowitą.
Najczęściej w takich dowodach korzystamy z:
- wyłączania wspólnego czynnika przed nawias
- przekształceń algebraicznych
- wzorów skróconego mnożenia
- analizy parzystości (parzyste / nieparzyste)
Dowody podzielności
Aby pokazać, że liczba a jest podzielna przez liczbę b, wystarczy zapisać ją w postaci:
a=b\cdot k
gdzie k jest liczbą całkowitą.
Oznacza to, że liczba a jest wielokrotnością liczby b, czyli przy dzieleniu przez b nie ma reszty.
Przykład. Udowodnij, że iloczyn czterech kolejnych liczb naturalnych jest podzielny przez 24.
Niech cztery kolejne liczby naturalne mają postać:
n, n+1, n+2, n+3
Rozważamy ich iloczyn:
n(n+1)(n+2)(n+3)
Wśród czterech kolejnych liczb zawsze:
- jedna jest podzielna przez 2
- jedna jest podzielna przez 4
- jedna jest podzielna przez 3
Dlaczego?
- co druga liczba jest parzysta (stąd podzielność przez 2)
- w każdej czwórce kolejnych liczb jedna jest podzielna przez 4
- w każdej trójce kolejnych liczb jedna jest podzielna przez 3
Zatem w iloczynie występują czynniki:
4 \cdot 3 \cdot 2 = 24
Możemy więc zapisać:
n(n+1)(n+2)(n+3) = 24 \cdot k
gdzie k jest liczbą całkowitą.
Dowiedliśmy, że iloczyn czterech kolejnych liczb naturalnych jest podzielny przez 24.
Dowody reszt z dzielenia
Aby pokazać, że liczba a przy dzieleniu przez b daje resztę r, wystarczy zapisać ją w postaci:
a=b\cdot k + r
gdzie k jest liczbą całkowitą, a r \in \left\{0, 1, \ldots, b - 1\right\}.
Przykład. Udowodnij, że jeśli liczba przy dzieleniu przez 4 daje resztę 3, to jej kwadrat przy dzieleniu przez 4 daje resztę 1.
Zapiszmy naszą liczbę (liczba przy dzieleniu przez 4 daje resztę 3):
a = 4k + 3
gdzie k jest liczbą całkowitą.
Podnieśmy ją do kwadratu i skorzystajmy ze wzoru skróconego mnożenia (kwadrat sumy):
a^2 = (4k + 3)^2 = (4k)^2 + 2\cdot4k\cdot3 + 3^2 = 16k^2 + 24k + 9
Mamy zbadać jej podzielność przez 4. Wyłączamy 4 przed nawias z części, która jest wielokrotnością 4:
a^2 = 16k^2 + 24k + 8 + 1 = 4(4k^2 + 6k + 2) + 1
Ponieważ 4k^2 + 6k + 2 jest liczbą całkowitą, oznacza to, że:
a^2 = 4m + 1
gdzie m jest liczbą całkowitą.
Zatem liczba a^2 przy dzieleniu przez 4 daje resztę 1.