Jako loppuosalla

Jako jäännöksellä on aritmeettinen operaatio , jolla on suuri rooli aritmetiikassa , lukuteoriassa , algebrassa ja kryptografiassa . Useimmiten tämä operaatio määritellään kokonaisluvuille tai luonnollisille luvuille seuraavasti [1] . Olkoon ja kokonaislukuja, ja jakaminen jäännöksellä (" jakoinen") tarkoittaa ("jakaja") kokonaislukujen löytämistä ja siten, että yhtäläisyys pätee: $a$ $b$ $b\neq 0.$ $a$ $b$ $q$ $r$

a=b\cdot q+r

Siten jaon tulokset jäännöksellä ovat kaksi kokonaislukua: kutsutaan jaon osittaisosamääräksi ja jaon loppuosa . Jakojäännökselle asetetaan lisäehto: toisin sanoen jaon loppuosan on oltava ei-negatiivinen luku ja itseisarvoltaan pienempi kuin jakaja . Tämä ehto varmistaa jakotulosten ainutlaatuisuuden jakojäännöksellä kaikille kokonaisluvuille, eli yhtälölle on ainutlaatuinen ratkaisu yllä olevissa olosuhteissa. Jos jäännös on nolla, sen sanotaan olevan jaollinen $q$ $r$ $0\leqslant r<|b|,$ $a=b\cdot q+r$ $a$ $b.$

Osittaisen osamäärän löytämistä kutsutaan myös kokonaislukujakoksi , ja jaon jäännösosan löytämistä kutsutaan jäännöksen ottamiseksi tai epämuodollisesti modulo-jakolliseksi (jälkimmäistä termiä tulee kuitenkin välttää, koska se voi johtaa sekaannukseen renkaassa jaossa tai ryhmä tähteitä analogisesti yhteen- tai kertolaskumoduulin kanssa ).

Esimerkkejä

Kun jaetaan positiivisen luvun jäännöksellä luvulla , saadaan epätäydellinen osamäärä ja jäännös . $a = 78$ $b = 33$ $q = 2$ $r = 12$

Tutkimus:

78=33\cdot 2+12.

Kun jaetaan negatiivisen luvun jäännöksellä luvulla , saadaan epätäydellinen osamäärä ja jäännös . $a = -78$ $b = 33$ $q = -3$ $r = 21$

Tutkimus:

-78=33\cdot (-3)+21.

Kun jaetaan negatiivisen luvun jäännöksellä luvulla , saadaan epätäydellinen osamäärä ja jäännös . $a=-9$ $b=-13$ $q=1$ $r = 4$

Tutkimus:

-9=1\cdot (-13)+4.

Kun jaetaan positiivisen luvun jäännöksellä luvulla , saadaan epätäydellinen osamäärä ja jäännös . $a=9$ $b=90$ $q = 0$ $r=9$

Tutkimus:

9=90\cdot 0+9.

Kun jaetaan luvun jäännöksellä, saadaan epätäydellinen osamäärä ja jäännös , eli jako suoritetaan kokonaisluvulla. $a = 78$ $b = 26$ $q = 3$ $r = 0$

Jakooperaatio jäännöksellä voidaan määrittää paitsi kokonaisluvuille myös muille matemaattisille objekteille (esimerkiksi polynomeille ), katso alla .

Määritelmä

Pysymällä tiukasti luonnollisten lukujen sisällä , on erotettava jäännöksellä jako ja kokonaisluvulla jako, koska nollajäännös ei ole luonnollinen luku; lisäksi epätäydellinen osamäärä jaettaessa pienempi luku suuremmalla tulee olla yhtä suuri kuin nolla, mikä johtaa myös luonnollisten lukujen ulkopuolelle. Kaikki nämä keinotekoiset rajoitukset vaikeuttavat formulaatioita tarpeettomasti, joten lähteissä yleensä joko otetaan huomioon laajennettu luonnollinen sarja , mukaan lukien nolla [2] , tai teoria muotoillaan välittömästi kokonaisluvuille, kuten edellä on osoitettu [1] .

Laskeaksesi positiivisella luvulla jaon osamäärän jakamalla (tavallisessa merkityksessä) tulos ja pyöristämällä tulos alaspäin lähimpään kokonaislukuun: $a$ $b$ $a$ $b$

q=\left\lfloor {\frac {a}{b}}\right\rfloor ,

kun .

b>0

jossa puolisulut tarkoittavat ottaen kokonaisluvun osan . Epätäydellisen osamäärän arvon avulla voit laskea jäännöksen arvon kaavalla: $\left\lfloor \cdot \right\rfloor$ $q$ $r$

r=ab\cdot q.

Negatiivista jakajaa varten sinun on pyöristettävä osamäärä ylöspäin:

q=\left\lceil {\frac {a}{b))\right\rceil ,

kun .

b<0

"Mod"-toiminto ja suhde vertailuihin

Jäännöksen arvo voidaan saada binäärioperaatiolla "ottaa jäännös" jakamisesta luvulla , jota merkitään mod : $a$ $b$

r=a{\bmod {b).

Tätä merkintää ei pidä sekoittaa modulo - vertailumerkintään . Kaava edellyttää vertailun suorittamista: $b$ $r$

r\equiv a{\pmod {b)),

Käänteinen implikaatio ei kuitenkaan yleensä pidä paikkaansa. Tämä vertailu ei nimittäin tarkoita jäännökseksi välttämättömän epätasa-arvon täyttymistä. $0\leqslant r<|b|$ $r$

Ohjelmoinnissa

Osaosamäärän ja jäännöksen laskeminen eri ohjelmointikielillä

Kieli	Epätäydellinen osamäärä	Loput	Jäljellä oleva merkki
ActionScript		%	Osinko
Ada		mod	Jakaja
Ada		rem	Osinko
PERUS	\	MOD	Määrittämätön
C (ISO 1990)	/	%	Määrittämätön
C (ISO 1999)	/	%	Jaettavissa [3]
C++ (ISO 2003)	/	%	Määrittämätön [4]
C++ (ISO 2011)	/	%	Jaettavissa [5]
C#	/	%	Osinko
kylmäfuusio		MOD	Osinko
Yhteinen Lisp		mod	Jakaja
Yhteinen Lisp		rem	Osinko
D	/	%	Jaettavissa [6]
Delfoi	div	mod	Osinko
eiffel	//	\\	Osinko
Erlang	div	rem	Osinko
Euforia		remainder	Osinko
Microsoft Excel (englanniksi)	QUOTIENT()	MOD()	Jakaja
Microsoft Excel (venäjä)	ЧАСТНОЕ()	ОСТАТ()	Jakaja
tiedostojen valmistaja	Div()	Mod()	Jakaja
Fortran		mod	Osinko
Fortran		modulo	Jakaja
GML (Game Maker)	div	mod	Osinko
mennä	/	%	Osinko
Haskell	div	mod	Jakaja
Haskell	quot	rem	Osinko
J		\|~	Jakaja
Java	/	%	Jaettavissa [7]
Java	Math.floorDiv	Math.floorMod	Jakaja (1,8+)
JavaScript	.toFixed(0)	%	Osinko
Lua		%	Jakaja
Mathematica	Quotient	Mod	Jakaja
MATLAB	idivide(?, ?, 'floor')	mod	Jakaja
MATLAB	idivide	rem	Osinko
MySQL	DIV	MOD %	Osinko
Oberon	DIV	MOD	+
Tavoite Caml		mod	Määrittämätön
Pascal	div	mod	Jaettavissa [8]
Perl	Ei	%	Jakaja
PHP	Ei [9]	%	Osinko
PL/I		mod	Jakaja ( ANSI PL/I )
Prolog (ISO 1995)		mod	Jakaja
PureBasic	/	Mod %	Osinko
Python	//	%	Jakaja
QBasic	\	MOD	Osinko
R	%/%	%%	Jakaja
RPG		%REM	Osinko
rubiini	/	%	Jakaja
Kaavio		modulo	Jakaja
SenseTalk		modulo	Jakaja
SenseTalk		rem	Osinko
tcl		%	Jakaja
Verilog (2001)		%	Osinko
VHDL		mod	Jakaja
VHDL		rem	Osinko
Visual Basic	\	Mod	Osinko

Jaon loppuosan löytämistä käytetään usein tietotekniikassa ja tietoliikennelaitteissa tarkistusnumeroiden ja satunnaislukujen luomiseen rajoitetulla alueella, kuten kongruenttisatunnaislukugeneraattorissa .

Lopun ottamisen toiminnot eri ohjelmointikielillä on esitetty oikealla olevassa taulukossa. Esimerkiksi Pascalissa operaatio modlaskee jaon loppuosan ja operaatio divsuorittaa kokonaislukujaon, jossa jaon loppuosa hylätään:

78 mod 33 = 12 78 div 33 = 2

Jäljelle jäävä merkki

Loppuosan ottaminen ohjelmointikielissä voi palauttaa negatiivisen tuloksen (negatiivinen osinko tai jakaja). Tässä on kaksi vaihtoehtoa:

Jäännöksen etumerkki on sama kuin osingon etumerkki: epätäydellinen osamäärä pyörii kohti nollaa.
Jäännöksen merkki on sama kuin jakajan merkki: epätäydellinen osamäärä pyörii . $-\infty$

Jos kielessä on molempien tyyppisiä jäännöksiä, kullakin niistä on oma osamääräoperaattorinsa. Molemmat toiminnot ovat tärkeitä.

On olemassa summa kopeikkoja, positiivisia tai negatiivisia. Muunna se rupliksi ja kopeikoiksi: ja . Jäännöksen etumerkki on sama kuin osingon etumerkki. $n$ n div 100n mod 100
Siellä on ääretön solukenttä, jokainen solu on 16 × 16 pikseliä. Mihin soluun piste ( , ) putoaa ja mitkä ovat koordinaatit suhteessa solun vasempaan yläkulmaan? Vastaus: ja vastaavasti. Jäännöksen etumerkki on sama kuin jakajan etumerkki. $x$ $y$ x div 16, y div 16(x mod 16, y mod 16)

Kuinka ohjelmoida, jos tällaista toimintoa ei ole?

Epätäydellinen osamäärä voidaan laskea jakamalla ja ottamalla kokonaislukuosa: , jossa , voi tehtävästä riippuen olla " lattia " tai katkaisu. Tässä jako on kuitenkin murtoluku , joka on paljon hitaampi kuin kokonaisluku. Tällaista algoritmia käytetään kielissä, joissa ei ole kokonaislukutyyppejä (erilliset laskentataulukot , ohjelmoitavat laskimet ja matemaattiset ohjelmat), sekä komentosarjakielissä , joissa tulkinnat ylittävät huomattavasti murto-aritmetiikka ( Perl , PHP ) ). $q=\left[{\frac {a}{b}}\oikea]$ $[x]$

Jos komentoa ei ole, modloppuosa ohjelmoidaan muodossa . $a-qb$

Jos positiivinen ja etumerkki on sama kuin osingon etumerkki, ei ole määritelty tai tuntematon, voit käyttää kaavaa löytääksesi ei-negatiivisen vähimmäisjäännöksen . $b$ $r$ $r'=(b+(a\operaattorinimi {mod}b))\operaattorinimi {mod}b$

Kahden potenssilla jaon epätäydellinen osamäärä ja ei-negatiivinen jäännös on bittisiirto ( merkittyille luvuille , aritmeettinen) ja . $2^{n}$ $a\gg n$ $a\mathop {\&} (2^{n}-1)$

Yleistykset

Reaaliluvut

Jos kaksi lukua ja (muu kuin nolla ) kuuluvat reaalilukujen joukkoon , voidaan jakaa ilman jäännöstä, ja osamäärä on myös reaaliluku. Jos ehdon osamäärän on oltava kokonaisluku , jäännös on tässä tapauksessa reaaliluku, eli se voi osoittautua murtoluvuksi . $a$ $b$ $a$ $b$

Muodollisesti:

jos , niin missä .

a,b\in {\mathbb {R)),b\neq 0

a=bq+r

0\leqslant r<|b|

Esimerkki

Jakamalla 7,9 luvulla 2,1 jäännöksellä saadaan:

\left\lfloor {\frac {7{,}9}{2{,}1}}\right\rfloor =3

(epätäydellinen osamäärä);

7{,}9-3\cdot 2{,}1=1{,}6

(loppu).

Gaussin kokonaisluvut

Gaussin luku on muodon kompleksiluku , jossa on kokonaislukuja. Niille voidaan määritellä jako jäännösjäännöksellä: mikä tahansa Gaussin luku voidaan jakaa jäännöksellä millä tahansa nollasta poikkeavalla Gaussin luvulla , eli se esitetään seuraavasti: $a+bi$ $a,b$ $u$ $v$

u=vq+r

jossa osamäärä ja jäännös ovat Gaussin lukuja, ja kuitenkin, toisin kuin kokonaisluvut, jaon loppuosa ei ole yksiselitteisesti määritelty. Voidaan esimerkiksi jakaa kolmeen tapaan: $q$ $r$ $|r|<|v|.$ $7+2i$ $3-i$

7+2i=(3-i)(2+i)+i=(3-i)(1+i)+3=(3-i)(2+2i)+(-1-2i) .

Polynomit

Kun jaetaan kahden polynomin jäännöksellä ja tuloksen yksilöllisyydelle, asetetaan ehto: jäännöspolynomin asteen on oltava tiukasti pienempi kuin jakajan aste: $f(x)$ $g(x)$

f(x)=q(x)g(x)+r(x)

, ja .

\deg(r)<\deg(g)

Esimerkki

{\frac {2x^{2}+4x+5}{x+1}}=2x+2

(loput 3 ), koska: .

2x^{2}+4x+5=(x+1)(2x+2)+3

Katso myös

Muistiinpanot

↑ 1 2 Division // Mathematical Encyclopedia (5 osassa) . - M . : Neuvostoliiton tietosanakirja , 1979. - T. 2.
↑ Potapov M. K., Alexandrov V. V., Pasichenko P. I. Algebra ja alkeisfunktioiden analyysi. M.: Nauka, 1981, 560 s., S. 9.
↑ ISO/IEC 9899:TC2: Kun kokonaisluvut jaetaan, /operaattorin tulos on algebrallinen osamäärä, jossa murto-osa hylätään. [Tätä kutsutaan usein "lyhentämiseksi nollaan".] ; muutosluettelossa 1999→TC1 ja TC1→TC2 tätä muutosta ei ole listattu.
↑ " ISO/IEC 14882:2003: Ohjelmointikielet -- C++ " , 5.6.4: International Organization for Standardization , International Electrotechnical Commission , 2003 . "binäärinen %-operaattori antaa ensimmäisen lausekkeen jaosta toisella jäännöksen. …. Jos molemmat operandit ovat ei-negatiivisia, loput ovat ei-negatiivisia; jos ei, jäännöksen etumerkki on toteutuksen määrittelemä" .
↑ N3242=11-0012 (työluonnos), sama teksti kuin C99
↑ D-kielimääritys (englanti) (linkki, jota ei voi käyttää) . dlang.org. Haettu 29. lokakuuta 2017. Arkistoitu alkuperäisestä 3. lokakuuta 2017.
↑ Arnold, Ken, Gosling, J. , Holmes, D. Java-ohjelmointikieli. - 3. painos - M., Pietari, Kiova: Williams, 2001. - S. 173-174. — ISBN 5-8459-0215-0 .
↑ 1973 standardi: div - jako katkaisulla .
↑ PHP: Aritmeettiset operaattorit - Manuaali . Käyttöpäivä: 27. marraskuuta 2014. Arkistoitu alkuperäisestä 19. marraskuuta 2014. (määrätön)