Wikipédia

„Maradékosztály” változatai közötti eltérés

Laptörténet interaktív böngészése
[ellenőrzött változat][nem ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Nincs szerkesztési összefoglaló
Javítás
1. sor:
{{lektor}}
 
Legyen az ''m'' egy 1-nél nagyobb [[természetes számok|természetes szám]]. Az [[egész számok]] szétválogathatók aszerint, hogy az ''m''-mel való [[maradékos osztás]] után mennyit adnak maradékul. Ha két egész szám az ''m''-mel maradékosan elosztva ugyanannyit ad maradékul, akkor azt mondjuk, hogy ez a két egész szám egymással [[kongruencia|kongruens]]. A kongruencia egy [[ekvivalenciareláció]], és az általa létrehozott [[ekvivalenciaosztály]]ok az ''m'' szerinti '''maradékosztály'''ok. Minden ''m'' esetében ''m'' darab különböző maradékosztály létezik.
Legyen az ''m'' egy [[természetes számok|természetes szám]]. Mivel a [[kongruencia]] ekvivalenciareláció, ezért osztályoz.
 
TetszőlegesSzabatosan megfogalmazva: tetszőleges <math>m \geq 2</math> [[egész számok|egész]] esetén az egész számok <math>\mathbb{Z}</math> halmaza ''m'' [[diszjunkt halmazok|diszjunkt]] osztály [[unió (halmazelmélet)|uniójára]] bomlik fel, mégpedig úgy, hogy <math>0 \leq i \leq m -1</math> esetén az ''i''-dik osztályban <math>k \cdot m + i</math> alakú számok vannak, ahol ''k'' végigfut az egészeken (más szóval, az ''i''-dik osztályba az ''m''-mel osztva ''i'' maradékot adó számok tartoznak). Ezeket az osztályokat ''m'' szerinti, vagy másképpen modulo ''modulom'' (rövid jelölése: mod ''m'') maradékosztályoknak nevezzük. A maradékosztályok jelentősége az, hogy ha két szám azonos maradékosztályba esik (modulo ''m''), akkor kongruensek egymással modulo ''m'', ha pedig különböző maradékosztályból valók, akkor nem kongruensek.
 
Egy modulo ''mod m'' maradékosztályból kiválasztott tetszőleges ''a'' elemet a maradékosztály ''reprezentáns elem''ének nevezzük, s azt mondjuk, hogy ''a'' reprezentálja a maradékosztályt.
 
A maradékosztályok [[fogalom|fogalmát]] [[Carl Friedrich Gauss]] vezette be 1801-es ''[[Disquisitiones Arithmeticae|Számelméleti vizsgálódások]]'' című művében.
 
== Példa ==
Legyen ''m'' = 5.
 
Ekkor 5 maradékosztály létezik
* a { ..., –20, –15, –10, –5, 0, 5, 10, 15, 20, ... } számhalmaz a 0-maradékosztály, azaz az 5·''i'' vagy 5·''i''+0 alakú számok, ahol ''i'' tetszőleges egész szám;
* a { ..., –19, –14, –9, –4, 1, 6, 11, 16, 21, ... } számhalmaz az 1-maradékosztály, azaz az 5·''i''+1 alakú számok, ahol ''i'' tetszőleges egész szám;
* a { ..., –18, –13, –8, –3, 2, 7, 12, 17, 22, ... } számhalmaza 2-maradékosztály, azaz az 5·''i''+2 alakú számok, ahol ''i'' tetszőleges egész szám;
* a { ..., –17, –12, –7, –2, 3, 8 13, 18, 23, ... } számhalmaz a 3-maradékosztály, azaz az 5·''i''+3 alakú számok, ahol ''i'' tetszőleges egész szám;
* a { ..., –16, –11, –6, –1, 4, 9, 14, 19, 24, ... } számhalmaz a 4-maradékosztály, azaz az 5·''i''+4 alakú számok, ahol ''i'' tetszőleges egész szám.
 
Általában 0, 1, 2, ..., (''m''-1) mod ''m'' maradékosztályokról beszélhetünk, ahol az egyszerűség kedvéért a 0, 1, 2, ... és ''m''-1 a megnevezésben szereplő reprezentáns elemek.
 
==Tulajdonságok==
A ''mod m'' maradékosztályok [[gyűrű (matematika)|gyűrűt]] alkotnak: összeadhatók, [[kivonás|kivonhatók]] és [[szorzás|szorozhatók]], de az [[osztás]] nem végezhető el reprezentáns elemekkel. [[Reciprok|Multiplikatív inverze]] ugyanis pontosan a [[redukált maradékosztály]]oknak van. Ezek minden eleme [[relatív prímek|relatív prím]] ''m''-hez. Ha ''m'' [[prímszámok|prím]], akkor az invertálás segítségével az osztás is definiálható; ekkor a maradékosztályok gyűrűje [[test (algebra)|test]].
 
Maradékosztályokkal úgy számolhatunk, hogy tetszőleges reprezentáns elemükkel számolunk, ugyanis a maradékosztályok elemei egymást helyettesíthetik az [[egyenlet]]ekben.
 
==Teljes maradékrendszer==
Ha minden egyesadott ''m'' darab egész szám, és közülük mindegyik más mod ''m'' maradékosztályt egy elem reprezentál, akkor ezek a számok '''teljes maradékrendszertmaradékrendszer'''t alkotnak.▼
 
==Fontosabb tételek==
▲Ha minden egyes ''mod m'' maradékosztályt egy elem reprezentál, akkor ezek a számok teljes maradékrendszert alkotnak.
===Tételek1. tétel===
'''Tétel''' - Néhány [[egész számok|egész szám]] teljes maradékrendszert alkot mod ''mod m'' [[akkor és csak akkor]], ha számuk ''m'', és nincs köztük két egymással kongruens szám.▼
 
'''Bizonyítás:''' - Legyen ''T''<sub>''m''</sub> teljes maradékrendszer mod ''mod m''. Minden maradékosztályból egy és csak egy elem van ''T''<sub>''m''</sub>-ben, ezért ''T''<sub>''m''</sub> elemszáma ''m''.▼
▲'''Tétel''' - Néhány [[egész számok|egész szám]] teljes maradékrendszert alkot ''mod m'' [[akkor és csak akkor]], ha számuk ''m'', és nincs köztük két egymással kongruens szám.
 
▲'''Bizonyítás''' - Legyen ''T''<sub>''m''</sub> teljes maradékrendszer ''mod m''. Minden maradékosztályból egy és csak egy elem van ''T''<sub>''m''</sub>-ben, ezért ''T''<sub>''m''</sub> elemszáma ''m''.
 
Mivel minden maradékosztályból egy elemet választottuk, ezért ''T''<sub>''m''</sub> elemei között nincs két szám, amely egymással kongruens.
23 ⟶ 39 sor:
Tekintsünk most ''m'' darab egész számot, amik között nincsenek [[kongruencia|kongruensek]]. Ezek csupa különböző maradékosztályba tartoznak, és mivel ''m'' darab van belőlük, azért az összes maradékosztály képviselve van.
 
=== 2. tétel===
'''Tétel''' - Legyen ''r''<sub>1</sub>, ''r''<sub>2</sub>, …, ''r''<sub>''m''</sub> teljes maradékrendszer ''mod ''m''. Legyen továbbá ''a'' [[relatív prím]] ''m''-hez, ''b'' tetszőleges egész szám. Ekkor ''ar''<sub>1</sub>+''b'', ''ar''<sub>2</sub>+''b'', …, ''ar''<sub>m</sub>+''b'' is teljes maradékrendszer ''mod m''.
 
'''Bizonyítás:''' - Az előző kritériumokra épül.
Sorra ellenőrizünk mindent:
 
Az új rendszer elemszáma ''m''.
 
Ha ''ar''<sub>''i''</sub>+''b'' és ''ar''<sub>''j''</sub>+''b'' kongruensek ''mod m'', akkor a [[kongruencia]] mindkét oldalából ''b''-t kivonva ''ar''<sub>''i''</sub> és ''ar''<sub>''j''</sub> kongruensek lennének. ''a'' relatív prím ''m''-hez, ezért lehet vele egyszerűsíteni. Kapjuk, hogy ''r''<sub>''i''</sub> és ''r''<sub>''j''</sub> kongruensek. Ez csak úgy lehet, hogy ''i'' = ''j''.
 
=== 3. tétel===
'''Tétel''' - Ha ''a'' kongruens ''b'' mod ''m'', akkor ''[[legnagyobb közös osztó|lnko]](''a'', ''m'') = lnko(''b'', ''m)'').
 
'''Bizonyítás:''' - A kongruencia azt jelenti, hogy ''b'' = ''a'' + mc''m''·''c'' valamely ''c'' egész számra. ''a'' és ''m'' is osztható lnko(''lnko(a,m) ''m)-mel, ezért ''lnko(''a'', ''m)'') ''b''-nek és ''m''-nek is közös osztója, így ''lnko(''a'', ''m)'') osztója ''lnko(''b'', ''m)'')-nek.
 
A fordított oszthatóság ugyanígy, szerepcserével adódik.
 
==Források==
* Freud Róbert - GyarmatiRóbert–Gyarmati Edit: ''Számelmélet'' (Tankönyvkiadó, 2000) ISBN 963 19 0784 8
 
{{portál|matematika|i |}}
 
[[Kategória:Számelmélet]]
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Maradékosztály”