Rozdělení se zbytkem

Dělení se zbytkem je aritmetická operace , která hraje velkou roli v aritmetice , teorii čísel , algebře a kryptografii . Nejčastěji je tato operace definována pro celá nebo přirozená čísla následovně [1] . Nechť a být celá čísla a dělení se zbytkem („dělitelný“) pomocí („dělitel“) znamená najít celá čísla a taková, že platí rovnost: $A$ $b$ $b\neq 0.$ $A$ $b$ $q$ $r$

a=b\cdot q+r

Výsledkem dělení se zbytkem jsou tedy dvě celá čísla: nazývaná částečný kvocient dělení a zbytek dělení . Na zbytek je kladena další podmínka: to znamená, že zbytek dělení musí být nezáporné číslo a v absolutní hodnotě menší než dělitel . Tato podmínka zajišťuje jednoznačnost výsledků dělení se zbytkem pro všechna celá čísla, to znamená, že za výše uvedených podmínek existuje jednoznačné řešení rovnice . Pokud je zbytek nula, říká se, že je dělitelný $q$ $r$ $0\leqslant r<|b|,$ $a=b\cdot q+r$ $A$ $b.$

Nalezení částečného kvocientu se také nazývá celočíselné dělení a nalezení zbytku dělení se nazývá převzetí zbytku nebo neformálně modulo dělení (poslednímu termínu je však třeba se vyhnout, protože může vést k záměně s dělením v kruhu nebo skupina zbytků analogicky s adičním nebo násobením modulo ).

Příklady

Při dělení se zbytkem kladného čísla dostaneme neúplný podíl a zbytek . $a=78$ $b=33$ $q=2$ $r=12$

Zkouška:

78=33\cdot 2+12.

Při dělení se zbytkem záporného čísla dostaneme neúplný podíl a zbytek . $a = -78$ $b=33$ $q=-3$ $r=21$

Zkouška:

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

Při dělení se zbytkem záporného čísla dostaneme neúplný podíl a zbytek . $a=-9$ $b=-13$ $q=1$ $r=4$

Zkouška:

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

Při dělení se zbytkem kladného čísla dostaneme neúplný podíl a zbytek . $a=9$ $b=90$ $q=0$ $r=9$

Zkouška:

9=90\cdot 0+9.

Při dělení se zbytkem čísla dostaneme neúplný kvocient a zbytek , tedy dělení se provede celé číslo. $a=78$ $b=26$ $q=3$ $r=0$

Operaci dělení se zbytkem lze definovat nejen pro celá čísla, ale i pro jiné matematické objekty (například pro polynomy ), viz dále .

Definice

Zůstat přísně uvnitř přirozených čísel , jeden musí rozlišovat mezi dělením se zbytkem a dělením celým číslem, protože nulový zbytek není přirozené číslo; navíc neúplný podíl při dělení menšího čísla větším by se měl rovnat nule, což vede i mimo přirozená čísla. Všechna tato umělá omezení formulace zbytečně komplikují, takže zdroje většinou buď uvažují s rozšířenou přirozenou řadou , včetně nuly [2] , nebo je teorie rovnou formulována pro celá čísla, jak je naznačeno výše [1] .

Chcete-li vypočítat částečný podíl dělení kladným číslem , vydělte (v obvyklém smyslu) a zaokrouhlete výsledek dolů na nejbližší celé číslo : $A$ $b$ $A$ $b$

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

kdy .

b>0

kde polozávorky označují převzetí celočíselné části . Hodnota neúplného podílu vám umožňuje vypočítat hodnotu zbytku pomocí vzorce: $\left\lfloor \cdot \right\rfloor$ $q$ $r$

r=ab\cdot q.

Pro záporného dělitele je třeba zaokrouhlit podíl nahoru:

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

kdy .

b<0

Operace "mod" a vztah k porovnáním

Hodnotu zbytku lze získat binární operací „vzít zbytek“ z dělení , označeno mod : $A$ $b$

r=a{\bmod {b).

Tato notace by neměla být zaměňována se srovnávací notací modulo . Vzorec pro znamená provést srovnání: $b$ $r$

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

obrácená implikace však obecně neplatí. Toto srovnání totiž neznamená naplnění nerovnosti nutné k tomu, aby byla zbytkem. $0\leqslant r<|b|$ $r$

V programování

Operace výpočtu parciálního podílu a zbytku v různých programovacích jazycích

Jazyk	Neúplný kvocient	Zbytek	Zbytek znamení
ActionScript		%	Dividenda
Ada		mod	Dělič
Ada		rem	Dividenda
ZÁKLADNÍ	\	MOD	Nedefinováno
C (ISO 1990)	/	%	Nedefinováno
C (ISO 1999)	/	%	Dělitelné [3]
C++ (ISO 2003)	/	%	Nedefinováno [4]
C++ (ISO 2011)	/	%	Dělitelné [5]
C#	/	%	Dividenda
studená fúze		MOD	Dividenda
Lisp obecný		mod	Dělič
Lisp obecný		rem	Dividenda
D	/	%	Dělitelné [6]
Delphi	div	mod	Dividenda
eiffel	//	\\	Dividenda
Erlang	div	rem	Dividenda
Euforie		remainder	Dividenda
Microsoft Excel (anglicky)	QUOTIENT()	MOD()	Dělič
Microsoft Excel (ruština)	ЧАСТНОЕ()	ОСТАТ()	Dělič
tvůrce souborů	Div()	Mod()	Dělič
Fortran		mod	Dividenda
Fortran		modulo	Dělič
GML (Game Maker)	div	mod	Dividenda
Jít	/	%	Dividenda
Haskell	div	mod	Dělič
Haskell	quot	rem	Dividenda
J		\|~	Dělič
Jáva	/	%	Dělitelné [7]
Jáva	Math.floorDiv	Math.floorMod	Oddělovač (1,8+)
JavaScript	.toFixed(0)	%	Dividenda
Lua		%	Dělič
Mathematica	Quotient	Mod	Dělič
MATLAB	idivide(?, ?, 'floor')	mod	Dělič
MATLAB	idivide	rem	Dividenda
MySQL	DIV	MOD %	Dividenda
Oberon	DIV	MOD	+
Cíl Caml		mod	Nedefinováno
Pascal	div	mod	Dělitelné [8]
Perl	Ne	%	Dělič
PHP	Ne [9]	%	Dividenda
PL/I		mod	Oddělovač ( ANSI PL/I )
Prolog (ISO 1995)		mod	Dělič
PureBasic	/	Mod %	Dividenda
Krajta	//	%	Dělič
QBasic	\	MOD	Dividenda
R	%/%	%%	Dělič
RPG		%REM	Dividenda
rubín	/	%	Dělič
Systém		modulo	Dělič
SenseTalk		modulo	Dělič
SenseTalk		rem	Dividenda
tcl		%	Dělič
Verilog (2001)		%	Dividenda
VHDL		mod	Dělič
VHDL		rem	Dividenda
Visual Basic	\	Mod	Dividenda

Nalezení zbytku dělení se často používá ve výpočetní technice a telekomunikačních zařízeních ke generování kontrolních čísel a generování náhodných čísel v omezeném rozsahu, například v generátoru kongruentních náhodných čísel .

Označení operace odebírání zbytku v různých programovacích jazycích jsou uvedeny v tabulce vpravo. Například v Pascalu operace modvypočítá zbytek dělení a operace divprovede celočíselné dělení, ve kterém je zbytek dělení zahozen:

78 mod 33 = 12 78 div 33 = 2

Znak zbytku

Operace převzetí zbytku v programovacích jazycích může vrátit záporný výsledek (pro zápornou dividendu nebo dělitele). Zde jsou dvě možnosti:

Znaménko zbytku je stejné jako znaménko dividendy: neúplný podíl se zaokrouhlí směrem k nule.
Znaménko zbytku je stejné jako znaménko dělitele: neúplný podíl se zaokrouhlí na . $-\infty$

Pokud má jazyk oba typy zbytků, každý z nich má svou vlastní operaci s částečným podílem. Obě operace jsou životně důležité.

Existuje součet kopejek, kladných nebo záporných. Převeďte jej na rubly a kopejky: a . Znaménko zbytku je stejné jako znaménko dividendy. $n$ n div 100n mod 100
Existuje nekonečné pole buněk, každá buňka má 16×16 pixelů. Do které buňky bod ( , ) spadá a jaké jsou souřadnice vzhledem k levému hornímu rohu buňky? Odpověď: resp . Znaménko zbytku je stejné jako znaménko dělitele. $X$ $y$ x div 16, y div 16(x mod 16, y mod 16)

Jak programovat, když taková operace neexistuje?

Neúplný podíl lze vypočítat vydělením a převzetím celé části: , kde , v závislosti na úloze, může být " podlaha " nebo zkrácení. Dělení je zde však zlomkové , což je mnohem pomalejší než celé číslo. Takový algoritmus se používá v jazycích, které nemají celočíselné typy (samostatné tabulky , programovatelné kalkulačky a matematické programy), stejně jako ve skriptovacích jazycích , ve kterých režie interpretace daleko převyšuje režii zlomkové aritmetiky ( Perl , PHP ). $q=\left[{\frac {a}{b}}\right]$ $[X]$

Pokud neexistuje žádný příkaz, modzbytek je naprogramován jako . $a-qb$

Pokud kladné a znaménko se shoduje se znaménkem dividendy, není definováno nebo neznámé, můžete použít vzorec k nalezení minimálního nezáporného zbytku . $b$ $r$ $r'=(b+(a\jméno operátora {mod}b))\jméno operátora {mod}b$

Neúplný kvocient a nezáporný zbytek po dělení mocninou dvou je bitový posun (pro čísla se znaménkem , aritmetika) a . $2^{n}$ $a\gg n$ $a\mathop {\&} (2^{n}-1)$

Zobecnění

Reálná čísla

Pokud dvě čísla a (jiná než nula ) patří do množiny reálných čísel , lze je beze zbytku dělit a podíl je také reálné číslo. Pokud musí být podíl podle podmínky celé číslo , v tomto případě bude zbytek reálné číslo, to znamená, že se může ukázat jako zlomkové . $A$ $b$ $A$ $b$

Formálně:

pokud , tak kde .

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

a=bq+r

0\leqslant r<|b|

Příklad

Vydělením 7,9 2,1 se zbytkem získáme:

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

(neúplný kvocient);

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

(zbytek).

Gaussova celá čísla

Gaussovo číslo je komplexní číslo tvaru , kde jsou celá čísla. Pro ně lze definovat dělení se zbytkem: libovolné Gaussovo číslo lze dělit se zbytkem libovolným nenulovým Gaussovým číslem , to znamená: $a+bi$ $a,b$ $u$ $proti$

u=vq+r

kde kvocient a zbytek jsou Gaussova čísla a , nicméně, na rozdíl od celých čísel, zbytek dělení není jednoznačně definován. Například lze rozdělit na tři způsoby: $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) .

Polynomy

Při dělení se zbytkem dvou polynomů a pro jednoznačnost výsledku je zavedena podmínka: stupeň zbývajícího polynomu musí být přísně menší než stupeň dělitele: $f(x)$ $g(x)$

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

a .

\deg(r)<\deg(g)

Příklad

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

(zbytek 3 ), protože: .

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

Viz také

Poznámky

↑ 1 2 Division // Matematická encyklopedie (v 5 svazcích) . - M .: Sovětská encyklopedie , 1979. - T. 2.
↑ Potapov M. K., Alexandrov V. V., Pasichenko P. I. Algebra a analýza elementárních funkcí. M.: Nauka, 1981, 560 s., S. 9.
↑ ISO/IEC 9899:TC2: Při dělení celých čísel je výsledkem /operátoru algebraický kvocient s vyřazenou částí. [To se často nazývá "zkrácení směrem k nule".] ; v seznamu změn 1999→TC1 a TC1→TC2 tato změna uvedena není.
↑ " ISO/IEC 14882:2003: Programovací jazyky -- C++ " , 5.6.4: Mezinárodní organizace pro normalizaci , Mezinárodní elektrotechnická komise , 2003 . "binární operátor % získá zbytek z dělení prvního výrazu druhým. …. Pokud jsou oba operandy nezáporné, pak je zbytek nezáporný; pokud ne, znaménko zbytku je definováno implementací“ .
↑ N3242=11-0012 (pracovní návrh), stejný text jako C99
↑ Specifikace jazyka D (angličtina) (nepřístupný odkaz) . dlang.org. Získáno 29. října 2017. Archivováno z originálu 3. října 2017.
↑ Arnold, Ken, Gosling, J. , Holmes, D. Programovací jazyk Java. - 3. vyd. - M., Petrohrad, Kyjev: Williams, 2001. - S. 173-174. — ISBN 5-8459-0215-0 .
↑ Standard z roku 1973: div - dělení se zkrácením .
↑ PHP: Aritmetické operátory – příručka . Datum přístupu: 27. listopadu 2014. Archivováno z originálu 19. listopadu 2014. (neurčitý)