WikiSysop: Bot: Automatski unos stranica

2021-12-08T14:12:28Z

Bot: Automatski unos stranica

Nova stranica

[[Datoteka:Clock group.svg|desno|220px|]]
Teoriju '''kongruencija''' uveo je veliki [[Njemačka|njemački]] [[matematika|matematičar]] [[Carl Friedrich Gauß|Carl Friedrich Gauss]], koji je ovu tehniku, poznatu i pod nazivom modularna aritmetika, zasnovao u svom djelu Disquisitiones Arithmeticae (''Istraživanja u aritmetici''), objavljenom [[1801.]] <ref>[https://fr.wikipedia.org/wiki/Disquisitiones_arithmeticae Disquisitiones arithmeticae]</ref>. Spomenuta knjiga se sastojala od sedam poglavlja, od kojih je prvih šest bilo posvećeno [[Teorija brojeva|teoriji brojeva]]. Svakodnevni primjer ove teorije srećemo pri mjerenju vremena, gdje koristimo takozvanu aritmetiku modulo 12 dijeleći dan na dva perioda u trajanju od dvanaest [[sat]]i.

== Motivacija ==
Ovdje ćemo navesti i objasniti spomenuti primjer. Neka kazaljka na zidnom satu pokazuje 13. Ona će pokazivati 13 za višekratnike (pozitivne i negativne) broja 12. Ipak, razlikujemo 1h i 13h. Dakle, u jednom danu (od 0h do 24h) kazaljka očito obiđe svaki broj dvaput, tj. ovdje gledamo [[Dijeljenje|ostatke]] prirodnih brojeva pri dijeljenju a 24.

Možemo zamisliti i da namatamo uže u krug s <math> m </math> brojeva. Slikovito, oni brojevi koji se na takav način "preklope" kažemo da su kongruentni '''modulo''' <math> m. </math>

== Definicija ==
Neka su <math> a, b </math> cijeli brojevi i <math> m </math> prirodan broj. Za brojeve <math> a </math> i <math> b </math> kažemo da su kongruentni po modulo <math> m </math> ako i samo vrijedi <math> m | a - b, </math> tj. samo ako <math> a, b </math> daju isti ostatak pri dijeljenju s <math> m. </math> Pišemo: <math> a - b \equiv 0 \pmod m, </math> odnosno <math> a \equiv b \pmod m. </math>

== Kongruentnost u <math> \mathbb{Z} </math> ==
Neka imamo prirodni broj <math> n. </math> Tada očito postoji točno <math> n </math> različitih ostataka pri dijeljenju s <math> n. </math>

U to se lako uvjerimo iz definicije ostatka. Svaki prirodni broj možemo napisati kao
<math> n = km + r, r = \{0, 1, 2, ...\}, n, k, m \in \mathbb{N}. </math> Broj <math> r </math> nazivamo ostatkom pri dijeljenju broja <math> n </math> s <math> m. </math> Za <math> r < 0 </math> nema smisla govoriti o "ostatku" kao takvom. Ipak, neka je <math> r
= \{0, 1, 2, ..., m\}. </math> Tada očito za <math> n = (k + i)m + r',r' := r - im, </math> tj. <math> r </math> postaje negativan. Vrijedi
<math> ... \equiv r - 2m \equiv r - m \equiv r \equiv r + m, \equiv r + 2m \equiv ... </math> Time smo dobili jednu svojevrsnu rezidualnu klasu. Dakle, tih klasa modulo <math> m </math> ima upravo <math> m. </math>

Na pozitivan ostatak možemo gledati kao na višak broja <math> n </math> da bude djeljiv s <math> m, </math> a na negativan ostatak kao na nedostajanje broja <math> n </math> da bude djeljiv s <math> m. </math>

== Operacije s kongurencijama ==
*Očito je da ako vrijedi <math> a \equiv b \pmod m, </math> onda je i <math> a \pm c \equiv b \pm c \pmod m, \forall c \in \mathbb{N}. </math>

*Posljedica ovoga je da vrijedi <math> ac \equiv bc \pmod m. </math> Obrnuto općenito ne vrijedi.

Primjerice, za
<math> 6 \equiv 3 \pmod 3 </math> nije <math> 2 \equiv 1 \pmod 3. </math>

*Naravno, vrijedi i <math> a \equiv b \pmod m \iff a^n \equiv b^n \pmod m. </math>

== Linearne kongruencije ==
Od svih kongruencija s polinomima, najjednostavnije su linearne kongruncije. To su kongruencije u obliku <math>ax \equiv b \pmod n.</math>

Postoji restrikcija rješenja karakteristična za linearne kongruencije koju ovdje navodimo.

Neka su dakle <math> a, m </math> prirodni, te <math> b </math> cijeli broj. Kongruencija <math> ax \equiv b \pmod m </math> ima rješenja ako i samo ako <math> d = M(a, m) </math> dijeli <math>b</math>. Ako je ovaj uvjet zadovoljen, onda gornja kongruencija ima točno <math>d </math> rješenja modulo <math>m</math>.

Za kongruencije s polinom stupnja <math>n</math> vrijedi poznati [[Lagrangeov teorem (teorija brojeva)|Lagrangeov teorem]].

== Mali Fermatov teorem ==
Jedan od temeljnih teorema u teoriji brojeva koji je usko vezan uz modularnu aritmetiku jest tzv. '''Mali Fermatov teorem,''' nazvan prema jednom od najistaknutijih matematičara [[17. stoljeće|17. stoljeća]], [[Francuska|francuskom]] matematičaru [[Pierre de Fermat|Pierreu de Fermatu]].

Ovako glasi iskaz toga važnog teorema. Neka je <math> p </math> prost broj i <math> a \in \mathbb{N} </math> takav da <math> p \nmid a. </math> Tada je <math> a^{p - 1} \equiv 1 \pmod p, </math> tj. <math> a^p \equiv a \pmod p </math>.

Fermatov teorem je poseban slučaj [[Eulerov teorem|Eulerovog teorema]] koji tvrdi da za svaka dva relativno prosta broja <math> a, n \in \mathbb{N} </math> vrijedi <math> a^{\varphi(n)} \equiv 1 \pmod n, </math> gdje je <math> \varphi(n) </math> Eulerova funkcija, odnosno funkcija koja svakom prirodnom broju pridružuje broj relativno prostih brojeva manjih od njega.

== Izvori ==
{{izvori}}
[[Kategorija:Aritmetika]]

Modularna aritmetika - Povijest promjena

WikiSysop: Bot: Automatski unos stranica