Kongruencje

$E=mc^2$

Kongruencje

Definicja co zapisujemy: Uwaga Dwie liczby całkowite przystają do siebie modulo $n$ wtedy i tylko wtedy, gdy dają tą samą resztę dzielenia przez $n$.
Przykłady
$10 \equiv 1\ ({\bmod {\ }}9)$, bo $10 – 1 $ dzieli liczbę 9.
$-1 \equiv 113\ ({\bmod{\ }}6)$, bo $113 + 1$ dzieli liczbę 6.
$-12 \equiv 13\ ({\bmod{\ }}5)$, bo $12 + 13$ dzieli liczbę 5.
$-5 \not \equiv 31\ ({\bmod{\ }}7)$, bo $31 + 5$ nie dzieli liczby 7.
Które z kongruencji są prawdziwe?
$-26 \equiv 44\ ({\bmod{\ }}10)$
$23 \equiv 71\ ({\bmod{\ }}11)$

Własności kongruencji

Przystawanie modulo $n$ jest relacją równoważnościową, tzn.:

• $a \equiv a\ ({\bmod {\ }}n)$ (zwrotność
• $a \equiv b\ ({\bmod {\ }}n) \Rightarrow b \equiv a\ ({\bmod {\ }}n)$ (symetryczność)
• $a \equiv b\ ({\bmod {\ }}n),\ b \equiv c\ ({\bmod {\ }}n) \Rightarrow a\equiv c\ ({\bmod{\ }}n)$(przechodniość)

Dowód

• $a \equiv a\ ({\bmod {\ }}n) \Rightarrow a – a$ jest podzielna przez liczbę n.
  
• $a \equiv b\ ({\bmod {\ }}n) \Rightarrow $ istnieje liczba całkowita $k$, że $a – b = k \cdot n \Rightarrow b – a = l \cdot n$, gdzie $l = -k$ jest liczbą całkowitą.
• $a \equiv b\ ({\bmod {\ }}n),\ b \equiv c\ ({\bmod {\ }}n) \Rightarrow $ istnieje liczba całkowita $k$, że $a – b = k \cdot n$, istnieje liczba całkowita $l$, że $b – c = l \cdot n $ Wtedy $a – c = a – b + b – c = k \cdot n + l \cdot n = (k+l)\cdot n = m \cdot n$, gdzie $m=k+l$ jest całkowita. Zatem
  $a \equiv c\ ({\bmod {\ }}n)$

Kongruencje można dodawać odejmować mnożyć stronami:

Przykładowo pokażemy dodawanie stronami:
$a \equiv b\ ({\bmod {\ }}n), \ c \equiv d\ ({\bmod {\ }}n) \Rightarrow$ istnieją liczby całkowite $k, l$ , że $a-b = k\cdot n$ oraz $c – d = l \cdot n \Rightarrow (a+c) – (b+d) = (a – b)+(c – d)= k\cdot n + l\cdot n = (k+l)\cdot n$, czyli $a+c \equiv $b+$d\ ({\bmod{\ }}n)$
Pozosta3e własności uzasadnij samodzielnie.
Z powyższej w3asności mamy:
Dodając do siebie $k$ razy kongruencja $\equiv b\ ({\bmod {\ }}n)$ dostajemy $ka \equiv kb\ ({\bmod {\ }}n)$, gdzie $k$ jest liczbą naturalną.
Analogicznie odejmując ją od siebie $l+1$ razy dostajemy $l \cdot a \equiv l \cdot b\ ({\bmod {\ }}n)$, gdzie l jest liczbą całkowitą ujemną.
Zatem $a \equiv b\ ({\bmod {\ }}n) \Rightarrow m \cdot a \equiv m \cdot b\ ({\bmod {\ }}n)$, gdzie $m$ jest dowolną liczbą cakowitą.
Wniosek 1 Z drugiej strony mnożąc przez siebie $k$ razy kongruencję $\equiv b\ ({\bmod {\ }}n)$ dostajemy $a^{k} \equiv b^{k} ({\bmod {\ }}n)$, gdzie $k$ jest liczbą naturalną.
Zatem $a \equiv b\ ({\bmod {\ }}n) \Rightarrow a^{k} \equiv b^{k} ({\bmod {\ }}n)$, gdzie $k$ jest dowolną liczbą naturalną.
Wniosek 2 Korzystając tych wniosków dodaniu stronami odpowiednich kongruencji mamy:
$a \equiv b\ ({\bmod {\ }}n) \Rightarrow a_{n} \cdot a^{n} + … +a_{1} \cdot a^{1} + a_{0} \equiv a_{n} \cdot b^{n} + … + a_{1} \cdot b^{1} + a_{0}$, gdzie $a_{n}, … , a_{0}$ są dowolnymi liczbami całkowitymi, a więc?
$f(a) \equiv f(b) \ ({\bmod {\ }}n)$, gdzie $f(x) = a_{n} \cdot x^{n} + … + a_{1} \cdot x + a_{0}$
Wniosek 3 Szczególnie w programowaniu pomocne są nastąjące równości:
W szczególności
$a+n \equiv a \ ({\bmod {\ }}n)$

Przykłady

Wyznaczyć ostatnią cyfrę liczby $2^{100000}$

Odp.
Należy wyznaczyć resztę z dzielenia przez 10
$$2^{4}\equiv 6 (\bmod 10)$$ $(2^{4})^{k} \equiv 6^{k}\equiv 6 (\bmod 10)$, gdzie k jest dowolną liczbą całkowitą dodatnią. (dowolna potęga liczby z cyfrą 6 na końcu nie zmienia tej cyfry)
dla k = 25000 otrzymujemy liczbę $2^{100000}$
Odp.
Ostatni± cyfr± liczby $2^{100000}$ jest 6.

Wyznaczyć cyfrę jednośści liczby $53^{53}-33^{33}$

Wyznaczamy resztę z dzielenia przez 10.
Zauważmy, że $53\equiv 3(\bmod 10)$, czyli $53^{53} \equiv 3^{53}(\bmod 10)$ oraz $33\equiv 3 (\bmod 10)$, czyli $33^{33}\equiv 3^{33}(\bmod 10)$.
Skoro $9\equiv -1 (\bmod 10)$, to $3^{53}=9^{26+1}=9^{26}\cdot 3 \equiv (-1)^{26}\cdot 3 (\bmod 10)\equiv 3(\bmod 10)$
Analogicznie $3^{33}= 9^{16}\cdot 3 \equiv (-1)^{16}\cdot 3 (\bmod 10) \equiv 3(\bmod 10)$
Korzystając z przechodniości kongruencji, odejmując je stronami mamy: $53^{53} – 33^{33} \equiv 3-3 (\bmod 10)$, czyli ta liczba jest podzielna przez 10.
Odp.
Ostatnią cyfrą liczby $53^{53}-33^{33}$ jest 0.

W jakim dniu tygodnia rozpoczęła się druga wojna światowa

Druga wojna światowa rozpoczęła się 1 września 1939 roku.
Przyporządkujmy dniom tygodnia cyfry od 0 do 6:
0 – niedziela, 1 – poniedziałek, 2 – wtorek, 3 – środa, 4 – czwartek, 5 – piątek, 6 – sobota.
Rok (nieprzestępny) ma 365 dni. $365= 350+14+1\equiv 1(\bmod 7)$. Stąd wynika, że po upływie roku (nieprzestępnego) numer dnia tygodnia wzrasta o 1 w porównaniu z rokiem poprzednim.
Rok przestępny ma 366 dni. $366 = 364+2=7\cdot 52 + 2 \equiv 2 (\bmod 7)$. Stąd wynika, że po upływie roku przestępnego numer dnia tygodnia wzrasta o 2.
Oznaczmy szukany dzień tygodnia przez $d$. Sprawdzamy w kalendarzu, że 01.01.2017 wypadał w piątek – 5. Od rozpoczęcia II wojny światowej upłynęło 78 lat. W tym okresie było $1940, 1944, 1948, … 2016$ roczników przestępnych. Daty tworzą ciąg arytmetyczny o różnicy 4. Ze wzoru obliczamy ich liczbę: $$a_{n}=a_{1}+(n-1)\cdot r$$ $$2016 = 1940+(n-1)\cdot 4$$ $$76=4n-4$$ $$4n=80$$ $$n=20$$ Zatem $$d\equiv 5 – 20 – 78=-93 (\bmod 7)\equiv 5 (\bmod 7).$$ Odp.
Druga wojna rozpoczęła się w piątek.

W jakim dniu tygodnia odbyła się bitwa pod Grunwaldem, która rozpoczęła się 15 lipca 1410 roku.

Rozumując podobnie jak wyżej od do 15.07.1410 do 15.07.2017(15.07.2017 wypadła sobota – 6) upłynęło dokładnie 607 lat. W tym okresie było $1412, 1416,…, 2016$ lat przestępnych z wyjątkiem roczników $1700, 1800, 1900$ (według kalendarza gregoriańskiego one nie s± przestępne). Zatem $$a_{n}=a_{1}+(n-1)\cdot 4$$ $$2016=1412+4n-4$$ $$608=4n$$ $$n=152$$ Zatem od rozpoczęcia bitwy pod Grunwaldem upłynęło $152-3=149$ lat przestępnych. Musimy jeszcze uwzględnić te pominięte 10 dni w kalendarzu. Zatem szukany dzień spełnia kongruencję: $$d\equiv 6-607-149+10=-740=-7\cdot 105-5(\bmod 7)\equiv 2 (\bmod 7)$$ Odp.
Bitwa pod Grunwaldem rozpoczęła się we wtorek.

Oblicz resztę z dzielenia liczby $77^{77}$ przez 5

Zauważmy, że $77\equiv 2(\bmod 5)$, czyli $77^{77}\equiv 2^{77}(\bmod 5)$ $$2^{77}=2^{76}\cdot 2 =4^{38}\cdot 2 \equiv (-1)^{38}\cdot 2\equiv 2(\bmod 5)$$ Odp.
Liczba $77^{77}$ przy dzieleniu przez 5 daje resztę 2.

Wyznaczyć dwie ostatnie cyfry liczby $99^{99}+49^{49}$

Należy wyznaczyć resztę z dzielenia przez 100. $$99^{99}\equiv (-1)^{99}\equiv -1 (\bmod 100)$$ Zauważamy, że $49^{2}=2401\equiv 1 (\bmod 100)$. St±d $$49^{49}=(49^{2})^{24}\cdot49 \equiv 1^{24}\cdot 49\equiv 49 (\bmod 100)$$ Dodaj±c stronami uzyskane kongruencje, mamy $$99^{99}+49^{49}\equiv -1+49=48(\bmod 100) $$ Odp.
Liczba $99^{99}+49^{49}$ kończy się na 48.
powrót do spisu