Kongruenca
- Za kongruenco v geometriji glej: Skladnost
Kongruénca oziroma kongruénčna relácija je ekvivalenčna relacija.
Celi števili in sta kongruentni po modulu ( je naravno število), če in samo če deli razliko števil in .
Definicija
urediNaj bo in . Pravimo, da je kongruenten po modulu ter to zapišemo kot:
- .
Velja natanko tedaj, ko velja .
Na primer , saj velja .
Lastnosti kongruenc
urediKongruenca je ekvivalenčna relacija, velja namreč:
Pravila pri računanju s kongruencami
urediIz definicije sledi da lahko kongruentna števila ali člene vedno zamenjujemo med seboj.
Naj za vse primere velja:
Seštevanje kongruenc
urediZgoraj pridobljeni enačbi seštejemo:
Množenje kongruenc
urediMnoženje kongruenc s celim številom
urediPotenciranje kongruenc
urediTa izrek je le posebni primer izreka o množenju kongruenc. Torej n-krat pomnožimo kongruenco samo s sabo in izrek je dokazan. Je pa ta izrek kot boste videli v nadaljevanju zelo pomemben.
Uporaba kongruenc
urediKongruence so uporabne predvsem v nalogah, kjer nastopajo števila prevelika za računanje z njimi brez računalnika. Tipične naloge, ki se jih navadno lotimo s kongruencami so:
- dokazovanje ali spodbijanje deljivosti
- ugotavljanje zadnje števke
- ugotavljenje ostanka pri deljenju z nekim številom
- uporaba v diofantskih enačbah
Primer naloge
uredi- S katero števko se konča ?
Ker iščemo zadnjo števko, gledamo število po modulu m=10. Velja seveda:
ali
in
Ker je 2005 = 4 * 501 + 1, velja
ali
pomnožimo obe strani s tri in to je rezultat
- .