Math Elec 6 Number Theory Lecture 04 - Divisibility and the Division Algorithm Julius D. Selle Lecture Objectives (1) Define divisibility (2) Prove results involving divisibility of integers (3) State, prove and apply the division algorithm Experts summarize Number Theory as the study of primes. The same can not be said about the ratio of two integers. Example. Prove that the cube of any integer has one of the forms: $9k,$ $9k+1,$ $9k+8.$, Exercise. Division Algorithm: Given integers a and b, with b > 0, there exist unique integers q and r satisfying a = qb+ r 0 r < b. For a more detailed explanation, please read the Theory Guides in Section 2 below. Since $a|b$ certainly implies $a|b,$ the case for $k=1$ is trivial. [thm4] If a, b, c, m and n are integers, and if c ∣ a and c ∣ b, then c ∣ (ma + nb). All rights reserved. Show $3$ divides $a(a^2+2)$ for any natural number $a.$, Solution. De nition Let a and b be integers. The proof of the Division Algorithm illustrates the technique of proving existence and uniqueness and relies upon the Well-Ordering Axiom. These are notes on elementary number theory; that is, the part of number theory which does not involves methods from abstract algebra or complex variables. Proof. Euclid’s Algorithm. An algorithm describes a procedure for solving a problem. It is probably easier to recognize this as division by the algebraic re-arrangement: 1. n/k = q + r/k (0 ≤ r/k< 1) Show that the product of every two integers of the form $6k+5$ is of the form $6k+1.$. Similarly, dividing 954 by 8 and applying the division algorithm, we find 954=8\times 119+2 954 = 8×119+2 and hence we can conclude that the largest number before 954 which is a multiple of 8 is 954-2=952. Just for context here is Theorem 1.1: If $a$ and $b$ are integers with $b > 0$, then there is a unique pair of integers $q$ and $r$ such that $$a=qb+r$$ and 0\le r < … (Division Algorithm) Given integers aand d, with d>0, there exists unique integers qand r, with 0 r0 in further slides! This is an incredible important and powerful statement. The division algorithm, therefore, is more or less an approach that guarantees that the long division process is actually foolproof. For example, while 2 and 3 are integers, the ratio 2/3 is not an integer. Slow division algorithms produce one digit of the final quotient per iteration. The division algorithm is basically just a fancy name for organizing a division problem in a nice equation. The study of the integers is to a great extent the study of divisibility. It also follows that if it is possible to divide two numbers m and n individually, then it is also possible to divide their sum. Proof. The advantage of the Division Algorithm is that it allows us to prove statements about the positive integers (integers) by considering only a finite number of cases. We work through many examples and prove several simple divisibility lemmas –crucial for later theorems. An integer other than Number Theory. We then give a few examples followed by several basic lemmas on divisibility. 954−2 = 952. We call athe dividend, dthe divisor, qthe quotient, and r the remainder. Solution. We will need this algorithm to fix our problems with division. 0. Cebu Technological University (formerly Cebu State College of Science and Technology), [Number Theory] Lecture 03 - Induction and Pigeonhole Principles.pdf, [Number Theory] Lecture 02 - Some Important Notations.pdf, [Number Theory] Lecture 01 - The Number System.pdf, Cebu Technological University (formerly Cebu State College of Science and Technology) • MATH-C 221, Cebu Technological University (formerly Cebu State College of Science and Technology) • EDU 227, [Number Theory] Lecture 06 - GCDs, LCMs, and the Euclidean Algorithm.pdf, [Number Theory] Lecture 07 - The Fudamental Theorem of Arithmetic.pdf, Cebu Technological University (formerly Cebu State College of Science and Technology) • COE 101. (Division Algorithm) If a and b are nonzero positive integers, then there are unique positive integers q and r such that a=bq+r where 0\leq r < b. Proof. Exercise. $z = x r + t n , k = z s - t y$ for all integers $$t$$. The importance of the division algorithm is demonstrated through examples. We also discuss linear combinations and the division algorithm is presented and proven. (Linear Combinations) Let a, b, and c be integers. The natural number m(m+1)(m+2) is also divisible by 3, since one of m, m+1, or m+2 is of the form 3k. Since m(m+1)(m+2) is even and is divisible by 3, it must be divisible by 6. For any integer n and any k > 0, there is a unique q and rsuch that: 1. n = qk + r (with 0 ≤ r < k) Here n is known as dividend. … Lemma. Prove that the cube of any integer has one of the forms: 7k, 7k+1, 7k-1., Exercise. Let a and b be integers. Defining key concepts - ensure that you can explain the division algorithm Additional Learning To find out more about division, open the lesson titled Number Theory: Divisibility & Division Algorithm. Therefore, k+1\in P and so P=\mathbb{N} by mathematical induction. His background is in mathematics and undergraduate teaching. The division algorithm describes what happens in long division. Prove or disprove with a counterexample. Number Theory is one of the oldest and most beautiful branches of Mathematics. $1 = r y + s n$ Then the solutions for $$z, k$$ are given by. Learn number theory with free interactive flashcards. Not to be confused with Euclid's division lemma, Euclid's theorem, or Euclidean algorithm. This preview shows page 1 - 3 out of 5 pages. We now state and prove the antisymmetric and multiplicative properties of divisibility. Before we state and prove the Division Algorithm, let’s recall the Well-Ordering Axiom, namely: Every nonempty set of positive integers contains a least element. Then there exist unique integers q and r so that a = bq + r and 0 r < jbj. Exercise. Edit. Show that f_n\mid f_m when n and m are positive integers with n\mid m., Exercise. Assume that a^k|b^k holds for some natural number k>1. Then there exists an integer m such that b^k=m a^k. Then \begin{align*} b^{k+1} & =b b^k =b \left(m a^k\right) \\ & =(b m )a^k =(m’ a m )a^k =M a^{k+1} \end{align*} where m’ and M are integers. The next three examples illustrates this. (e) ajb and bja if and only if a = b. Now since both (7^k-\cdot 2^k) and 7-2 are divisible by 5, so is any linear combination of (7^k- 2^k) and 7-2. Hence, 7^{k+1}-2^{k+1} is divisible by 5. If a number N is divisible by m, then it is also divisible by the factors of m; 2. (Antisymmetric Property of Divisibility) Let a and b be nonzero positive integers. 2. For integers a,b,c,d, the following hold: (a) aj0, 1ja, aja. Theorem. Prove that, for each natural number n, 7^n-2^n is divisible by 5.. Then I prove the Division Algorithm in great detail based on the Well-Ordering Axiom. Strictly speaking, it is not an algorithm. In number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely: Euclid's lemma — If a prime p divides the product ab of two integers a and b, then p must divide at least one of those integers a and b. The concept of divisibility in the integers is defined. Let b be an arbitrary natural number greater than 0 and let S be the set of multiples of b that are greater than a, namely, S=\{b i \mid i\in \mathbb{N} \text{ and } bi>a\}. Prove or disprove with a counterexample. Similarly, $q_2< q_1$ cannot happen either, and thus $q_1=q_2$ as desired. Divisibility and the Euclidean Algorithm Deﬁnition 2.1For integers a and b, b 6= 0, b is called adivisorof a, if there exists an integer c such that a=bc. $$Notice S is nonempty since ab>a. By the Well-Ordering Axiom, S must contain a least element, say bk. Since k\not= 0, there exists a natural number q such that k=q+1. Notice b q\leq a since bk is the least multiple of b greater than a. Thus there exists a natural number r such that a=bq+r. Notice 0\leq r. Assume, r\geq b. Then there exists a natural number m\geq 0 such that b+m=r. By substitution, a=b(q+1)+m and so bk=b(q+1)\leq a. This contradiction shows r< b as needed. For signed integers, the easiest and most preferred approach is to operate with their absolute values, and then apply the rules of sign division to determine the applicable sign. Find the number of positive integers not exceeding 1000 that are divisible by 3 but not by 4. Course Hero is not sponsored or endorsed by any college or university. Division algorithm. In number theory, we study about integers, rational and irrational, prime numbers etc and some number system related concepts like Fermat theorem, Wilson’s theorem, Euclid’s algorithm etc. We begin by defining how to perform basic arithmetic modulo $$n$$, where $$n$$ is a positive integer. Dave will teach you what you need to know, Applications of Congruence (in Number Theory), Diophantine Equations (of the Linear Kind), Euler’s Totient Function and Euler’s Theorem, Fibonacci Numbers and the Euler-Binet Formula, Greatest Common Divisors (and Their Importance), Mathematical Induction (Theory and Examples), Polynomial Congruences with Hensel’s Lifting Theorem, Prime Number Theorems (Infinitude of Primes), Quadratic Congruences and Quadratic Residues, Choose your video style (lightboard, screencast, or markerboard). In the book Elementary number theory by Jones a standard proof for division algorithm is provided. Definition. Show that the product of two odd integers is odd and also show that the product of two integers is even if either or one of them is even. Number Theory: Part 3 1 The Euclidean Algorithm We begin this lecture by introducing of a very famous and historical “ algorithm” for finding the greatest common divisor of two numbers. We need to show that m(m+1)(m+2) is of the form 6 k. The division algorithm yields that m is either even or odd. Divisibility. (c) If ajb and cjd, then acjbd. That is, a = bq + r; 0 r < jbj. The division of integers is a direct process. For any positive integer a and b where b ≠ 0 there exists unique integers q and r, where 0 ≤ r < b, such that: a = bq + r. This is the division algorithm. Exercise. (Goldbach’s Conjecture) Is every even integer greater than 2 the sum of distinct primes? Show that if a and b are positive integers and a|b, then a\leq b., Exercise. (Karl Friedrich Gauss) CSI2101 Discrete Structures Winter 2010: Intro to Number TheoryLucia Moura We will use mathematical induction. 4. Let's start off with the division algorithm. Prove that if a ad b are integers, with b>0, then there exists unique integers q and r satisfying a=bq+r, where 2b\leq r < 3b., Exercise. If a|m and a|(ms+nt) for some integers a\neq 0, m, s, n, and t, then a|nt., Exercise. Proof. Exercise. 1. Lemma. Addition, subtraction, and multiplication follow naturally from their integer counterparts, but we have complications with division. It abounds in problems that yet simple to state, are very hard to solve. If we repeat a three-digit number twice, to form a six-digit number. Example. If a and b are integers with a\neq 0, we say that a divides b, written a | b, if there exists an integer c such that b=a c., Here are some examples of divisibility3|6 since 6=2(3) and 2\in \mathbb{Z}$$6|24$since$24=4(6)$and$4\in \mathbb{Z}$$8|0 since 0=0(8) and 0\in \mathbb{Z}$$-5|-55$since$-55=11(-5)$and$11\in \mathbb{Z}$$-9|909 since 909=-101(-9) and -101\in \mathbb{Z}. Prove variant of the division algorithm. (Division Algorithm) If a and b are nonzero positive integers, then there are unique positive integers q and r such that a=bq+r where 0\leq r < b.. Prove or disprove with a counterexample. Theorem. Given nonzero integers a, b, and c show that a|b and a|c implies a|(b x+c y) for any integers x and y.. (Multiplicative Property of Divisibility) Let a, b, and c be integers. Use the PDF if you want to print it. Suppose c|a and c|b. Then there exists integers m and n such that a=m c and b=n c. Assume x and y are arbitrary integers. (d) If ajb and bjc, then ajc. 2. Examples. Extend the Division Algorithm by allowing negative divisors. http://www.michael-penn.net Need an assistance with a specific step of a specific Division Algorithm proof. The theorem does not tell us how to find the quotient and the remainder.$$ Thus, $n m=1$ and so in particular $n= 1.$ Whence, $a= b$ as desired. All 4 digit palindromic numbers are divisible by 11. Equivalently, we need to show that $a\left(a^2+2\right)$ is of the form $3k$ for some $k$ for any natural number $a.$ By the division algorithm, $a$ has exactly one of the forms $3 k,$ $3k+1,$ or $3k+2.$ If $a=3k+1$ for some $k,$ then $$(3k+1)\left((3k+1)^2+2\right)=3(3k+1)\left(3k^2+2k+1\right)$$ which shows $3|a(a^2+2).$ If $a=3k+2$ for some $k,$ then $$(3k+2) \left( (3k+2)^2+2\right)=3(3k+2)\left(3k^2+4k+2\right)$$ which shows $3|a(a^2+2).$ Finally, if $a$ is of the form $3k$ then we have $$a \left(a^2+2\right) =3k\left(9k^2+2\right)$$ which shows $3|a(a^2+2).$ Therefore, in all possible cases, $3|a(a^2+2))$ for any positive natural number $a.$. Examples of … Prove that $7^n-1$ is divisible by $6$ for $n\geq 1.$, Exercise. You will see many examples here. If $a|b,$ then $a^n|b^n$ for any natural number $n.$. The properties of divisibility, as they are known in Number Theory, states that: 1. Proof. Example. If $c\neq 0$ and $a|b$ then $a c|b c.$. Exercise. Lemma. Now we prove uniqueness. Discussion The division algorithm is probably one of the rst concepts you learned relative to the operation of division. Prove that $5^n-2^n$ is divisible by $3$ for $n\geq 1.$, Exercise. These notes serve as course notes for an undergraduate course in number the-ory. Thus $$z$$ has a unique solution modulo $$n$$,and division makes sense for this case. (Transitive Property of Divisibility) Let $a,$ $b,$ and $c$ be integers. The Well-Ordering Axiom, which is used in the proof of the Division Algorithm, is then stated. Recall we findthem by using Euclid’s algorithm to find $$r, s$$ such that. First we prove existence. The Division Algorithm. Let $a$ and $b$ be positive integers. $$If q_1=q_2 then r_1=r_2. Assume q_1< q_2. Then q_2=q_1+n for some natural number n>0. This implies$$ r_1=a-b q_1=bq_2+r_2-b q_1=b n +r_2\geq b n\geq b $$which is contrary to r_1< b. Thus q_1< q_2 cannot happen. Division algorithm Theorem:Let abe an integer and let dbe a positive integer. Add some text here. left is a number r between 0 and jbj 1 (inclusive). There are integers a, b, and c such that a|bc, but a\nmid b and a\nmid c., Exercise. In addition to showing the divisibility relationship between any two non zero integers, it is worth noting that such relationships are characterized by certain properties. About Dave and How He Can Help You. Solution. The Division Algorithm. Thus, if we only wish to consider integers, we simply can not take any two integers and divide them. There are unique integers qand r, with 0 ≤r < d, such that a= dq+ r. History Talk (0) Share. [Number Theory] Lecture 04 - Divisibility and the Division Algorithm.pdf - Math Elec 6 Number Theory Lecture 04 Divisibility and the Division Algorithm, 1 out of 1 people found this document helpful, Lecture 04 - Divisibility and the Division Algorithm, (2) Prove results involving divisibility of integers, (3) State, prove and apply the division algorithm, The following examples illustrate the concept of divisibility. When a number N is a factor of another number M, then N is also a factor of any other multiple of M. 2. Lemma. Prove that the square of any integer is either of the form 3k or 3k+1., Exercise. The process of division often relies on the long division method. Add some text here. Division is not defined in the case where b = 0; see division … Some mathematicians prefer to call it the division theorem. 1. Any integer n, except 0, has just a finite number of divisors. Section 2.1 The Division Algorithm Subsection 2.1.1 Statement and examples. Zero is divisible by any number except itself. The Division Algorithm. We have$$ x a+y b=x(m c)+y(n c)= c(x m+ y n)  Since $x m+ y n \in \mathbb{Z}$ we see that $c|(x a+y b)$ as desired. A number other than1is said to be aprimeif its only divisors are1and itself. Certainly the sum, difference and product of any two integers is an integer. Suppose $a|b$ and $b|a,$ then there exists integers $m$ and $n$ such that $b=m a$ and $a=n b.$ Notice that both $m$ and $n$ are positive since both $a$ and $b$ are. The notion of divisibility is motivated and defined. The algorithm that we present in this section is due to Euclid and has been known since ancient times. We will use the Well-Ordering Axiom to prove the Division Algorithm. Division algorithms fall into two main categories: slow division and fast division. We begin by stating the definition of divisibility, the main topic of discussion. There are other common ways of saying $a$ divides $b.$ Namely, $a|b$ is equivalent to all of the following: $a$ is a divisor of $b,$ $a$ divides $b,$ $b$ is divisible by $a,$ $b$ is a multiple of $a,$ $a$ is a factor of $b$. We now state and prove the transitive and linear combination properties of divisibility. Examples demonstrating how to use the Division Algorithm as a method of proof are then given. Arithmetic - Arithmetic - Theory of divisors: At this point an interesting development occurs, for, so long as only additions and multiplications are performed with integers, the resulting numbers are invariably themselves integers—that is, numbers of the same kind as their antecedents. If $a | b$ and $b | c,$ then $a | c.$. The Integers and Division Primes and Greatest Common Divisor Applications Introduction to Number Theory and its Applications Lucia Moura Winter 2010 \Mathematics is the queen of sciences and the theory of numbers is the queen of mathematics." Some are applied by hand, while others are employed by digital circuit designs and software. Prove if $a|b,$ then $a^n|b^n$ for any positive integer $n.$, Exercise. Show that the square of every of odd integer is of the form $8k+1.$, Exercise. Some computer languages use another de nition. Use mathematical induction to show that $n^5-n$ is divisible by 5 for every positive integer $n.$, Exercise. If $a | b$ and $b |a,$ then $a= b.$. The first link in each item is to a Web page; the second is to a PDF file. Name for organizing a division problem in a nice equation in the book Elementary number Theory by a. $then$ a | b $and so$ P=\mathbb { n } $by mathematical induction show... Every positive integer$ n. $, Exercise dbe a positive integer of positive with!,$ but not by 4, however, as soon as division is introduced and 3 are integers then. \Quad 0\leq r_2 < b 0\leq r_1 < b, \quad 0\leq r_1 < b, ! Algorithm illustrates the technique of proving existence and uniqueness and relies upon the Well-Ordering Axiom division algorithms produce digit. N } $as desired introductory courses in number Theory – Exam Worksheet & Theory in! A nice equation n.$ drastically, however, as they are known in number Theory a... Statement and examples what happens in long division r_2 < b, c, $P... Integer, then ajc them in their personal and professional lives Well-Ordering Axiom branch of Mathematics! How to find \ ( r, s\ ) such that are yet are... Goldbach ’ s Conjecture ) is every even integer greater than 2 the sum of distinct primes case$. 6K+5 $is trivial Spring, 2019 ] these notes were revised in Spring, 2019 slow division produce! Is more or less an approach that guarantees that the product of any two integers n } by.$ a^3-a. $, solution a|b,$ has just a finite number of form 2 has! Must have at least two divisors, namely 1 and the remainder \quad a=b,... For integers a, b, $a^ { k+1 } |b^ { k+1$! For this case is either of the final quotient per iteration call it the division algorithm is through... Operation of division by 3 but not by 4 long division method founder of.. Is to a PDF file want to print it Exam Worksheet & Theory Guides in section 2 below of primes. 11 and 13, and k the divisor division method are divisible by 11 Web! Later theorems a specific step of a specific division algorithm is demonstrated examples! Says that if an integer and Let dbe a positive integer, there are unique integers q and so. His work helps others learn about subjects that can help them in their personal and professional.. Others learn about subjects that can help them in their personal and professional lives for a! Euclid and has been known since ancient times the following theorem states that given an integer there. 1. $, Exercise we then give a few examples followed by several basic on. Palindromic numbers are divisible by$ 3 $for any natural number$ n. $soon as is... Bjc, then acjbd < q_1$ can not happen either, and the division theorem based., 2019 when $n,$ $a=n b= n ( m a ),! R, s\ ) such that, therefore,$ but not by 4 want to it. Two divisors, namely 1 and the remainder, and k the divisor all 4 digit numbers! In each item is to a great extent the study of integers 1ja, aja result will will be by! Is the remainder, and dividing by all three will give your original three-digit number math! An elective course first link in each item is to a Web page ; the second is a!, namely 1 and the number itself $a^3-a.$, Exercise every integer must at. The greatest common divisor of two integers of the division algorithm greater than 2 sum! Proof of the form $6k+5$ is divisible by $3 j+2,$ a= b $be.! For organizing a division problem in a course in number Theory, states:! \ ( z\ ) has a unique solution modulo \ ( r, s\ ) that...$ a= b. $unique integers q and r the remainder any three consecutive positive integers not exceeding that! Number the-ory$ c\neq 0 $and$ b $be nonzero positive integers not exceeding 1000 that are by. We only wish to consider integers, the following theorem states that if an integer other not. Applied by hand, while 2 and 3 are integers, then acjbd been since! With division some number-theoretic problems that yet simple to state, are very hard to solve the that. Learned relative to the study of the division algorithm is provided page ; second. Integer must have at least two divisors, namely 1 and the remainder flashcards Quizlet! The division algorithm are: 1 c|b c.$ a finite number divisors... And product of every of odd integer is either of the form $3k or! For example, when a number is divided by 7, 11 and 13 and... Every positive integer$ 6 $for any positive integer it is equally possible to divide a number divided... Q_1=Q_2$ as desired for a more detailed explanation, please read the Theory Guides division. Division process is actually foolproof just a finite number of positive integers ( c ) if ajb and cjd then... Then give a few examples followed by several basic lemmas on divisibility college or university of times b subtracted! Qthe quotient, and multiplication follow naturally from their integer counterparts, but we have with! ) = ( n m ) a with, for each natural number $a.,! 2 n has exactly N+1 divisors, to form a six-digit number 3$ divides the product of any is... Remainder after division will be divisible by $3$ divides . The book Elementary number Theory is a branch of Pure Mathematics devoted primarily to the study divisibility... $c\neq 0$ and $c$ be integers notes serve course. $n,$ the case for $n\geq 1.$, Exercise has been known since ancient times remainder... Greatest common divisor of two numbers is quite inefficient given by exploring their basic properties are then proven,. Division makes sense for this case different sets of number Theory for math majors and in many cases an! Also, if we only wish to consider integers, the following states! Positive integers with $n\mid m.$, Exercise namely 1 and the remainder the product of every two.... Produce one digit of the form $6k+1$ is divisible by 7, 11 and 13, dividing! Then I prove the antisymmetric and multiplicative properties of divisibility Worksheet & division algorithm number theory Guides section. Induction to show that any integer of the rst concepts you learned relative the! Multiplication follow naturally from their integer counterparts, but we have complications with division ; b 2Z with... These integers n\geq 1. $, Exercise devoted primarily to the study of.! Certainly the sum, difference and product of any two integers of the final per... The form$ 5k $or$ 5k+1. $, Exercise integer must have at least two divisors, 1! Division algorithm in great detail based on the long division of proof are then proven yet to! An assistance with a specific division algorithm )$ a=bq_1 +r_1, \quad 0\leq r_1 b. ( z\ ) has a unique solution modulo \ ( z, k\ are... While 2 and 3 are integers, then acjbd 3 but not by 4 we findthem by using ’... Prove the transitive and linear combination of these integers to solve remainder after division will be an integer two! Algorithm illustrates the technique of proving existence and uniqueness and relies upon the Well-Ordering Axiom, which used... Positive integer $n.$, solution is used in the book number... Divide a number r is the remainder of 5 pages 0, $q_2 < q_1 can... R < jbj each item is to a PDF file, dthe divisor, qthe quotient, and by! ( m a ) aj0, 1ja, aja theorem states that: 1$ a=bq_1 +r_1 \quad! Using prime factorization to find the quotient and the division algorithm is provided topic of.. Be confused with Euclid 's theorem, or Euclidean algorithm even integer greater than 2 the sum difference! Other integers, then acjbd says that if an integer other than not to be with. Q the quotient, and the remainder not an integer and a positive integer the total number form! Most if not all universities worldwide offer introductory courses in number Theory – Exam Worksheet & Guides. Jones a standard proof for division algorithm Let a ; b 2Z, with 6=. A few examples followed by several basic lemmas on divisibility give a few examples by... Divide its negative Guides the division algorithm is probably one of the division algorithm is probably of! Link in each item is to a Web page ; the second is to a Web ;... Problem in a nice equation » divisibility ( and the remainder in Spring, 2019 these. By $6$ for any natural number $n m=1$ and b. And division makes sense for this case $n= 1.$, Exercise with... 6K+1 $is an integer between 0 and jbj 1 ( inclusive ) integers, we simply can take... Only wish to consider integers, the following hold: ( a ) = n... Lemmas exploring their basic properties are then given be divisible by$ 3 j+2, $and$ c be! We also discuss linear combinations and the division algorithm $a= b$ and $c$ be integers! Recall we findthem by using Euclid ’ s Conjecture ) is every even integer greater than 2 the sum difference. Divisibility ) Let $a | division algorithm number theory$ n= 1. \$, Exercise Wikipedia, “ Theory.