Division med resten

Division med rest är en aritmetisk operation som spelar en stor roll inom aritmetik , talteori , algebra och kryptografi . Oftast definieras denna operation för heltal eller naturliga tal enligt följande [1] . Låta och vara heltal, och division med en rest ("delbart") med ("divisor") betyder att hitta heltal och sådant att likheten gäller: $a$ $b$ $b\neq 0.$ $a$ $b$ $q$ $r$

a=b\cdot q+r

Resultaten av division med en rest är alltså två heltal: kallas den partiella kvoten av divisionen och resten av divisionen . Ett ytterligare villkor ställs på resten: det vill säga att resten av divisionen måste vara ett icke-negativt tal och i absolut värde mindre än divisorn . Detta villkor säkerställer unikheten hos resultatet av divisionen med en återstod för alla heltal, det vill säga det finns en unik lösning på ekvationen under ovanstående förhållanden. Om resten är noll sägs den vara delbar med $q$ $r$ $0\leqslant r<|b|,$ $a=b\cdot q+r$ $a$ $b.$

Att hitta partialkvoten kallas också heltalsdivision och att hitta resten av en division kallas att ta resten eller, informellt, modulo division (dock bör den senare termen undvikas, eftersom det kan leda till förväxling med division i en ring eller grupp av rester i analogi med addition eller multiplikation modulo ).

Exempel

När vi dividerar med en rest av ett positivt tal med , får vi en ofullständig kvot och en rest . $a=78$ $b=33$ $q=2$ $r=12$

Undersökning:

78=33\cdot 2+12.

När vi dividerar med en rest av ett negativt tal med , får vi en ofullständig kvot och en rest . $a=-78$ $b=33$ $q=-3$ $r=21$

Undersökning:

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

När vi dividerar med en rest av ett negativt tal med , får vi en ofullständig kvot och en rest . $a=-9$ $b=-13$ $q=1$ $r=4$

Undersökning:

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

När vi dividerar med en rest av ett positivt tal med , får vi en ofullständig kvot och en rest . $a=9$ $b=90$ $q=0$ $r=9$

Undersökning:

9=90\cdot 0+9.

När vi dividerar med en rest av ett tal med får vi en ofullständig kvot och en rest , det vill säga divisionen utförs heltal. $a=78$ $b=26$ $q=3$ $r=0$

Divisionsoperationen med en rest kan definieras inte bara för heltal utan även för andra matematiska objekt (till exempel för polynom ), se nedan .

Definition

Förbli strikt inom de naturliga talen måste man skilja mellan division med en rest och division med heltal, eftersom nollresten inte är ett naturligt tal; dessutom bör den ofullständiga kvoten när man dividerar ett mindre tal med ett större vara lika med noll, vilket också leder bortom naturliga tal. Alla dessa konstgjorda begränsningar komplicerar i onödan formuleringarna, så källorna brukar antingen betrakta den utökade naturliga serien , inklusive noll [2] , eller så formuleras teorin omedelbart för heltal, som indikerat ovan [1] .

För att beräkna den partiella kvoten av division med ett positivt tal , dividera (i vanlig mening) med och avrunda resultatet nedåt till närmaste heltal: $a$ $b$ $a$ $b$

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

när .

b>0

där halvparenteser anger att ta heltalsdelen av . Värdet på den ofullständiga kvoten låter dig beräkna värdet på resten med hjälp av formeln: $\left\lfloor \cdot \right\rfloor$ $q$ $r$

r=ab\cdot q.

För en negativ divisor måste du avrunda kvoten uppåt:

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

när .

b<0

"Mod"-operationen och relation till jämförelser

Värdet på resten kan erhållas genom den binära operationen att "ta resten" från division med , betecknad med mod : $a$ $b$

r=a{\bmod {b).

Denna notation bör inte förväxlas med modulo-jämförelsenotation . Formeln för innebär att man utför en jämförelse: $b$ $r$

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

den omvända implikationen är dock inte sant i allmänhet. Denna jämförelse innebär nämligen inte uppfyllelsen av den ojämlikhet som krävs för att vara en rest. $0\leqslant r<|b|$ $r$

I programmering

Operationen att beräkna delkvoten och resten på olika programmeringsspråk

Språk	Ofullständig kvot	Återstoden	Resten tecken
ActionScript		%	Utdelning
Ada		mod	Delare
Ada		rem	Utdelning
GRUNDLÄGGANDE	\	MOD	Odefinierad
C (ISO 1990)	/	%	Odefinierad
C (ISO 1999)	/	%	Delbar [3]
C++ (ISO 2003)	/	%	Odefinierad [4]
C++ (ISO 2011)	/	%	Delbar [5]
C#	/	%	Utdelning
kall fusion		MOD	Utdelning
Vanlig Lisp		mod	Delare
Vanlig Lisp		rem	Utdelning
D	/	%	Delbar [6]
Delphi	div	mod	Utdelning
eiffel	//	\\	Utdelning
Erlang	div	rem	Utdelning
Eufori		remainder	Utdelning
Microsoft Excel (engelska)	QUOTIENT()	MOD()	Delare
Microsoft Excel (ryska)	ЧАСТНОЕ()	ОСТАТ()	Delare
filtillverkare	Div()	Mod()	Delare
Fortran		mod	Utdelning
Fortran		modulo	Delare
GML (Game Maker)	div	mod	Utdelning
gå	/	%	Utdelning
Haskell	div	mod	Delare
Haskell	quot	rem	Utdelning
J		\|~	Delare
Java	/	%	Delbar [7]
Java	Math.floorDiv	Math.floorMod	Avdelare (1,8+)
JavaScript	.toFixed(0)	%	Utdelning
Lua		%	Delare
Mathematica	Quotient	Mod	Delare
MATLAB	idivide(?, ?, 'floor')	mod	Delare
MATLAB	idivide	rem	Utdelning
MySQL	DIV	MOD %	Utdelning
Oberon	DIV	MOD	+
Mål Caml		mod	Odefinierad
Pascal	div	mod	Delbar [8]
Perl	Inte	%	Delare
PHP	Nej [9]	%	Utdelning
PL/I		mod	Avdelare ( ANSI PL/I )
Prolog (ISO 1995)		mod	Delare
PureBasic	/	Mod %	Utdelning
Pytonorm	//	%	Delare
QBasic	\	MOD	Utdelning
R	%/%	%%	Delare
RPG		%REM	Utdelning
rubin	/	%	Delare
Schema		modulo	Delare
SenseTalk		modulo	Delare
SenseTalk		rem	Utdelning
tcl		%	Delare
Verilog (2001)		%	Utdelning
VHDL		mod	Delare
VHDL		rem	Utdelning
Visual Basic	\	Mod	Utdelning

Att hitta resten av en division används ofta i datorteknik och telekommunikationsutrustning för att generera kontrollnummer och generera slumptal inom ett begränsat intervall, till exempel i en kongruent slumptalsgenerator .

Beteckningarna för operationen att ta resten på olika programmeringsspråk presenteras i tabellen till höger. Till exempel i Pascal beräknar operationen modresten av en division, och operationen divutför en heltalsdivision, där resten av divisionen kasseras:

78 mod 33 = 12 78 div 33 = 2

Resten tecken

Operationen med att ta resten i programmeringsspråk kan ge ett negativt resultat (för en negativ utdelning eller divisor). Det finns två alternativ här:

Tecknet för återstoden är detsamma som utdelningens tecken: den ofullständiga kvoten avrundar mot noll.
Restens tecken är detsamma som divisorns tecken: den ofullständiga kvoten avrundas till . $-\infty$

Om ett språk har båda typerna av rester, har var och en av dem sin egen partiella kvotoperation. Båda operationerna är viktiga.

Det finns en summa kopek, positiv eller negativ. Konvertera det till rubel och kopek: och . Tecknet på återstoden är detsamma som tecknet på utdelningen. $n$ n div 100n mod 100
Det finns ett oändligt cellfält, varje cell är 16×16 pixlar. Vilken cell faller punkten ( , ) in i, och vilka är koordinaterna i förhållande till cellens övre vänstra hörn? Svar: och respektive. Restens tecken är detsamma som divisorns tecken. $x$ $y$ x div 16, y div 16(x mod 16, y mod 16)

Hur programmerar man om det inte finns någon sådan operation?

Den ofullständiga kvoten kan beräknas genom att dividera och ta heltalsdelen: , där , beroende på uppgiften, kan vara ett " golv " eller en trunkering. Däremot är divisionen här bråkdel , vilket är mycket långsammare än heltal. En sådan algoritm används i språk som inte har heltalstyper (separata kalkylblad , programmerbara miniräknare och matematiska program), såväl som i skriptspråk , där tolkningskostnaderna vida överstiger overheaden för fraktionerad aritmetik ( Perl , PHP ). $q=\vänster[{\frac {a}{b}}\höger]$ $[x]$

Om det inte finns något kommando, programmeras modresten som . $a-qb$

Om positivt, och tecknet sammanfaller med utdelningens tecken, inte är definierat eller okänt, kan du använda formeln för att hitta den minsta icke-negativa återstoden . $b$ $r$ $r'=(b+(a\operatörsnamn {mod}b))\operatörsnamn {mod}b$

Den ofullständiga kvoten och den icke-negativa resten av division med en potens av två är en bitförskjutning (för tecken med tecken , aritmetik) och . $2^{n}$ $a\gg n$ $a\mathop {\&} (2^{n}-1)$

Generaliseringar

Reella tal

Om två tal och (annat än noll ) tillhör uppsättningen av reella tal , kan delas med utan rest, och kvoten är också ett reellt tal. Om kvoten per villkor måste vara ett heltal , i det här fallet kommer resten att vara ett reellt tal, det vill säga det kan visa sig vara bråktal . $a$ $b$ $a$ $b$

Formellt:

om , då , var .

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

a=bq+r

0\leqslant r<|b|

Exempel

Att dividera 7,9 med 2,1 med en rest ger:

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

(ofullständig kvot);

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

(återstoden).

Gaussiska heltal

Ett Gaussiskt tal är ett komplext tal av formen , där är heltal. För dem kan division med en rest definieras: vilket gaussiskt tal som helst kan delas med en rest med valfritt Gaussiskt tal som inte är noll , det vill säga representeras som: $a+bi$ $a,b$ $u$ $v$

u=vq+r

där kvoten och återstoden är gaussiska tal, och dock, till skillnad från heltal, är resten av divisionen inte unikt definierad. Kan till exempel delas in i tre sätt: $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) .

Polynom

När man dividerar med en återstod av två polynom och för att resultatet ska vara unikt, införs ett villkor: graden av återstodspolynomet måste vara strikt mindre än graden av divisor: $f(x)$ $g(x)$

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

, och .

\deg(r)<\deg(g)

Exempel

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

(återstoden 3 ), eftersom: .

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

Se även

Anteckningar

↑ 1 2 Division // Mathematical Encyclopedia (i 5 volymer) . - M . : Soviet Encyclopedia , 1979. - T. 2.
↑ Potapov M. K., Alexandrov V. V., Pasichenko P. I. Algebra och analys av elementära funktioner. M.: Nauka, 1981, 560 s., S. 9.
↑ ISO/IEC 9899:TC2: När heltal delas är resultatet av /operatorn den algebraiska kvoten med eventuell bråkdel kasserad. [Detta kallas ofta "trunkering mot noll".] ; i listan över ändringar 1999→TC1 och TC1→TC2 är denna förändring inte listad.
↑ " ISO/IEC 14882:2003: Programmeringsspråk -- C++ " , 5.6.4: International Organization for Standardization , International Electrotechnical Commission , 2003 . "den binära %-operatorn ger resten från divisionen av det första uttrycket med det andra. …. Om båda operanderna är icke-negativa är resten icke-negativa; om inte, är tecknet på resten implementeringsdefinierat" .
↑ N3242=11-0012 (Arbetsutkast), samma text som C99
↑ D-språkspecifikation (engelska) (otillgänglig länk) . dlang.org. Hämtad 29 oktober 2017. Arkiverad från originalet 3 oktober 2017.
↑ Arnold, Ken, Gosling, J. , Holmes, D. The Java Programming Language. - 3:e uppl. - M., St. Petersburg, Kiev: Williams, 2001. - S. 173-174. — ISBN 5-8459-0215-0 .
↑ 1973 års standard: div - division med trunkering .
↑ PHP: Arithmetic Operators - Manual . Datum för åtkomst: 27 november 2014. Arkiverad från originalet 19 november 2014. (obestämd)