Division with remainder of integers
division of integers
Арифметикада Евклидтік бөлу – немесе қалдықпен бөлу – бір бүтін санды (бөлшектің) екіншісіне (бөлгішке) бөлу процесі болып табылады, оның нәтижесінде бүтін санның бөліндісі және бөлгіштің абсолюттік мәнінен кіші табиғи санның қалдығы шығады. Негізгі қасиет – бөлінді мен қалдық белгілі бір шарттарда болады және бірегей болады. Осы бірегейлігінің арқасында Евклидтік бөлу көбінесе есептеудің нақты әдісіне сілтеме жасамай және бөлінді мен қалдықты нақты есептемей қарастырылады. Есептеу әдістері бүтін санды бөлу алгоритмдері деп аталады, олардың ең танымал әдісі – бағанмен бөлу. Евклидтік бөлу және оны есептеу алгоритмдері бүтін сандарға қатысты көптеген мәселелер үшін маңызды, мысалы, екі бүтін санның ең үлкен ортақ бөлгішін табу үшін Евклидтік алгоритмі және модульдік арифметика, онда тек қалдықтар қарастырылады. Тек қалдықты есептеуден тұратын операция модульдік операция деп аталады және математика мен компьютерлік ғылымда жиі қолданылады.
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than the absolute value of the divisor. A fundamental property is that the quotient and the remainder exist and are unique, under some conditions. Because of this uniqueness, Euclidean division is often considered without referring to any method of computation, and without explicitly computing the quotient and the remainder. The methods of computation are called integer division algorithms, the best known of which being long division. Euclidean division, and algorithms to compute it, are fundamental for many questions concerning integers, such as the Euclidean algorithm for finding the greatest common divisor of two integers, and modular arithmetic, for which only remainders are considered. The operation consisting of computing only the remainder is called the modulo operation, and is used often in both mathematics and computer science.
Тарих
"Евклидтік бөлу" Евклидтің есімімен аталғанымен, оның бар болу және бірегейлік теоремасын білмегендігі сезіледі, ал ол білген жалғыз есептеу әдісі – қайталап шығару арқылы бөлу еді. 13 ғасырда Фибоначчи Еуропаға енгізген индус-араб сандар жүйесі ашылғанға дейін бөлу өте қиын болды, және оны тек ең білікті математиктер ғана орындай алатын. Қазіргі кезде көптеген бөлу алгоритмдері, соның ішінде ұзын бөлу, осы жазу тәсіліне немесе оның екілік сандар сияқты түрлеріне негізделген. Бірақ Ньютон-Рафсон бөлінісі – ерекше жағдай, ол кез келген сандар жүйесіне тәуелсіз. "Евклидтік бөлу" термині 20 ғасырда "Евклидтік сақиналардың бөлінуі" деген ұғымды қысқарту үшін пайда болды. Математиктер осы бөлуді сандарды бөлудің басқа түрлерінен ажырату мақсатында оны жылдам қабылдады.
Although "Euclidean division" is named after Euclid, it seems that he did not know the existence and uniqueness theorem, and that the only computation method that he knew was the division by repeated subtraction. Before the discovery of Hindu–Arabic numeral system, which was introduced in Europe during the 13th century by Fibonacci, division was extremely difficult, and only the best mathematicians were able to do it. Presently, most division algorithms, including long division, are based on this notation or its variants, such as binary numerals. A notable exception is Newton–Raphson division, which is independent from any numeral system. The term "Euclidean division" was introduced during the 20th century as a shorthand for "division of Euclidean rings". It has been rapidly adopted by mathematicians for distinguishing this division from the other kinds of division of numbers.
Интуитивті мысал
Бір пирогтың 9 кесегі бар, оларды 4 адамға тең бөліп беруге болады. Евклидтік бөлуді пайдаланып, 9-ды 4-ке бөлгенде 2 бүтін, қалдығы 1 болады. Яғни, әр адам 2 кесектен пирог алады, ал 1 кесек қалады. Бұл көбейту арқылы, бөлудің кері амалымен растауға болады: егер 4 адамның әрқайсысы 2 кесек алса, онда барлығы 4 × 2 = 8 кесек берілген болады. Қалған 1 кесекті қоссақ, нәтижесі 9 кесекке тең болады. Қорыта айтқанда: 9 = 4 × 2 + 1. Жалпы, егер кесектер санымен белгіленсе, ал адамдар санымен белгіленсе, онда пирогты адамдар арасында тең бөліп беруге болады, мұнда әр адам кесек алады (бөлінді), ал қалған кесектер саны (қалдық) болады. Осы жағдайда теңдеуі орындалады. Егер 9 кесек 4 емес, 3 адамға бөлінсе, онда әрқайсысы 3 кесек алады және ешқандай кесек қалмайды, яғни қалдық 0-ге тең болады, соның салдарынан 3 саны 9-ды қалдықсыз бөледі, немесе 3 саны 9-ға бөлінеді деуге болады. Евклидтік бөлуді теріс бөлшектің (немесе теріс бөлгіштің) жағдайында да сол формуланы қолдану арқылы кеңейтуге болады; мысалы, −9 = 4 × (−3) + 3, яғни −9-ды 4-ке бөлгенде −3 бүтін, қалдығы 3 болады.
Suppose that a pie has 9 slices and they are to be divided evenly among 4 people. Using Euclidean division, 9 divided by 4 is 2 with remainder 1. In other words, each person receives 2 slices of pie, and there is 1 slice left over. This can be confirmed using multiplication, the inverse of division: if each of the 4 people received 2 slices, then 4 × 2 = 8 slices were given out in total. Adding the 1 slice remaining, the result is 9 slices. In summary: 9 = 4 × 2 + 1. In general, if the number of slices is denoted and the number of people is denoted , then one can divide the pie evenly among the people such that each person receives slices (the quotient), with some number of slices being the leftover (the remainder). In which case, the equation holds. If 9 slices were divided among 3 people instead of 4, then each would receive 3 and no slice would be left over, which means that the remainder would be zero, leading to the conclusion that 3 evenly divides 9, or that 3 divides 9. Euclidean division can also be extended to negative dividend (or negative divisor) using the same formula; for example −9 = 4 × (−3) + 3, which means that −9 divided by 4 is −3 with remainder 3.
Мысалдар
Егер a = 7 және b = 3 болса, онда q = 2 және r = 1, себебі 7 = 3 × 2 + 1. Егер a = 7 және b = −3 болса, онда q = −2 және r = 1, себебі 7 = −3 × (−2) + 1. Егер a = −7 және b = 3 болса, онда q = −3 және r = 2, себебі −7 = 3 × (−3) + 2. Егер a = −7 және b = −3 болса, онда q = 3 және r = 2, себебі −7 = −3 × 3 + 2.
If a = 7 and b = 3, then q = 2 and r = 1, since 7 = 3 × 2 + 1. If a = 7 and b = −3, then q = −2 and r = 1, since 7 = −3 × (−2) + 1. If a = −7 and b = 3, then q = −3 and r = 2, since −7 = 3 × (−3) + 2. If a = −7 and b = −3, then q = 3 and r = 2, since −7 = −3 × 3 + 2.
Дәлел
Бөлу теоремасының келесі дәлелі теріс емес бүтін сандардың кеміту тізбегінің әрдайым тоқтауына негізделген. Ол екі бөлікке бөлінеді: бірі – бар екенін көрсету үшін, екіншісі – бірегейлігін көрсету үшін. Басқа дәлелдемелер жақсы реттелгендік принципін (яғни, теріс емес бүтін сандардың бос емес кез келген жиынында ең кішкентай элемент болады деген тұжырым) қолданып, ойды жеңілдетуге тырысады, бірақ бөлуді шешуге тікелей алгоритм ұсынбау кемшілігіне ие (толығырақ ақпарат алу үшін қараңыз).
The following proof of the division theorem relies on the fact that a decreasing sequence of non negative integers stops eventually. It is separated into two parts: one for existence and another for uniqueness of and Other proofs use the well ordering principle (i. e., the assertion that every non empty set of non negative integers has a smallest element) to make the reasoning simpler, but have the disadvantage of not providing directly an algorithm for solving the division (see for more).