problems and proofs in numbers and algebra pdf

Beginning Number Concepts and Prime Numbers

This article provides an overview of the set of all integers (Z) and the set of all positive integers (N), introducing the fundamental operations involving integers and the essential components of prime numbers These mathematical symbols and concepts will be consistently referenced throughout the text.

Definition Ifaandbare integers anda¤0, thenaDIVIDESb(orais aDIVISOR ofb) if there is an integercsuch that acDb: (1.1.1)

In this case, we also say that (i)ais aDIVISOR ofb, (ii)ais aFACTOR ofb, or (iii)bis aMULTIPLEofa.

Notation We will writeajbto mean thatadividesborbisDIVISIBLEbya The symbola−bmeans that “adoes not divideb.” Thus3j9but4−9.

When a variable ¤ is not equal to zero, there exists a real number, c, that satisfies the equation (1.1.1); however, this solution may not be an integer The key aspect of divisibility is that the solution c to the equation (1.1.1) must be an integer.

The symbol \(3 | 6\) indicates that 6 is divisible by 3, meaning there exists an integer \(c\) such that \(3c = 6\), with \(c = 2\) as the solution Conversely, \(3 \nmid 8\) signifies that no integer \(c\) satisfies \(3c = 8\) Although there is a fraction \(x = \frac{8}{3}\) that satisfies \(3x = 8\), since \(\frac{8}{3} = 2 \frac{2}{3}\) is not an integer, it confirms that 3 does not divide 8.

Divisibility can be defined by two key properties The first property states that if an integer divides two numbers, it also divides both their sum and their difference.

Exercise 1 Ifajbandajcthen prove thataj.bCc/andaj.bc/.

Exercise 2 Leta; b; c2Z Then prove that

B Ifa dividesb anda dividesc, then, for any integersk and l,a divides the integerkbClc.

Prime numbers serve as the fundamental building blocks of integers, much like atoms are the basic units of molecules In this article, we will define key terms and present the Fundamental Theorem of Arithmetic (Theorem 1), which provides a precise mathematical framework for understanding prime numbers We assume you are already familiar with the concept of prime numbers, so we will focus on the theorem without delving into extensive examples.

Definition Ifn is an integer andn > 1thennis aPRIME NUMBER if the only

6 1 Number Concepts, Prime Numbers, and the Division Algorithm

We saynis aCOMPOSITE NUMBERifn > 1and not a prime number.

Starting with an integer greater than 1, such as 315, we can explore its factors until we reach the fundamental components This process illustrates the mathematical concept of expressing an integer as a product of its prime numbers, which serve as the basic building blocks of all integers.

A prime number, \( n \), actually has four divisors: 1, \( n \), and two additional divisors that are often overlooked While it is commonly believed that a prime number has only two positive divisors, the definition clarifies that it includes 1 and the number itself, making the total count four.

There are 5 ways to factor 315 into 2 numbers (ignoring order) Here are 4 of them (935is the fifth).

Each of these can be further factored to give rise to the trees (they are actually called “factor trees”) below.

The Fundamental Theorem of Arithmetic states that every integer greater than one can be uniquely factored into prime numbers In our analysis, we consistently find that the factorization includes two 3's, one 5, and one 7, all of which are prime numbers The proof of this theorem involves advanced concepts, which are not covered in this article.

It is also referred to as “UNIQUE PRIME FACTORIZATION” because315D3 2 57.

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a product of prime numbers, with some primes potentially repeated This prime factorization is unique, disregarding the order of the factors.

The statement of uniqueness in prime factorization indicates that the prime factors of a number are consistent, regardless of their order, and the frequency of each prime factor, known as multiplicity, remains unchanged For example, the prime factors of 315 are 3, 5, and 7, with the prime number 3 appearing twice, which is expressed as "3 has multiplicity 2."

By collecting like primes and replacing them by a single factor, we can rephrase Theorem1as a corollary:

Any positive integer \( n > 1 \) can be uniquely expressed as a product of prime numbers in the form \( n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} \), where each \( k_i \) is a positive integer, \( p_i \) represents prime numbers, and the primes are arranged in increasing order \( p_1 < p_2 < \ldots < p_r \) This unique representation is known as the Prime Power Decomposition of \( n \).

This article assumes the reader has a basic understanding of set notation and the concept of a set as a collection of objects, without requiring formal knowledge of set theory properties We will provide a brief overview of key notations, including union, intersection, empty sets, and disjoint sets It is important to note that the foundational concept of a set was introduced by mathematician Georg Cantor (1845–1918).

Notation We sayxis an ELEMENT of the setAifxis a member ofAand we write

To define a set, we can either enumerate all its elements within braces or establish a rule that characterizes the set In this notation, the symbol “|” is read as “such that.” For instance, let A represent the set of integers ranging from 1 to a specified upper limit.

10 inclusive Then we can writeAin two distinct ways:

In mathematical notation, the symbol “j” serves two distinct purposes: it signifies “such that” in set descriptions, while in the context of integers, it indicates division For instance, the expression 7j21 is a true statement regarding divisibility, unrelated to set construction Additionally, new sets can be created from existing ones, such as sets A and B, through various methods.

The most useful constructions are the intersection ofAandB(which consists of all elements which are common toAandB) and union ofAandB(which consists of those elements which are inAorB).

Definition TheEMPTY SET, written;, is the set with no elements in it.

Definition If A andB are sets then the INTERSECTION OF A AND B, written

If A represents the set of integers that are multiples of 3 and B denotes the set of integers that are multiples of 2, then the difference A \ B comprises the integers that are multiples of 6.

Definition IfAandBare sets, theUNION OFAANDB, writtenA[B, is given by

Remark The term “or” in the definition is inclusive In other words,x 2 A[B means eitherxis inAorxis inB(orxis in bothAandB.)

Definition Ifn2Zandnis divisible by2, thennis called anEVEN INTEGER(or just “even”) Ifn2Zis not even, thennisODD.

Of course,nD0is even and so we can represent the sets of even and odd integers respectively as:

Even IntegersD fn2ZjnD2kfor somek2Zg; and

Odd IntegersD fm2ZjmD2lC1for somel2Zg:

Example 1 Prove that the sum of any two even integers is even.

Solution Letnandmbe even We must show that.nCm/is twice some integer. Since both are even, by the definition of “even”, there are integers`1and`2with nD2`1andmD2`2

ThusnCmD2` 1 C2` 2 D2.` 1 C` 2 /and sonCmis twice the integer` 1 C` 2 which is the definition ofnCmbeing even //

Exercise 3 Prove that the sum of any two odd integers is even.

Divisibility of Some Combinations of Integers

This section presents two distinct types of results related to divisibility The first type includes general results, such as the principle that if an integer divides two other integers, it also divides their sum The second type challenges the reader to identify all integers that meet specific divisibility conditions, exemplified by the problem of finding non-negative integers \( n \) such that \( 3n^8 \) divides \( 2n + 3 \).

Both types of problems begin with a variable name, typically "n," and inquire about the conditions under which a statement is true The first type yields a universal answer, such as "all n" or specific categories like "all odd n" or "all even n." In contrast, the second type provides a limited set of values of n that satisfy the condition Notably, results from the first type, like "The product of two consecutive numbers is even," can be applied to both problem types To tackle subsequent examples and exercises, it's beneficial to assign variable names to the integers involved and utilize basic algebra Remember, for an odd integer n, it can be expressed as 2k + 1 for some k in the integers This technique was similarly employed in Example 1, focusing on the sum of even integers.

Example 4 Show that the sum of 3 consecutive integers is always divisible by three.

Solution Letn 2 Z The three consecutive integers are thenn,nC1, andnC2 and so the sum of three consecutive integers, calledsis sDnC.nC1/C.nC2/D3nC3D3.nC1/:

Thussis 3 times an integer and so3js //

Note One can also let the three consecutive integers ben1,n, andnC1. The generalization of Example4is interesting See Problem1 of the Problem Set1.2.

Example 5 Ifaandbare odd, then prove thata 2 b 2 is divisible by8.

Solution Sinceaandbare both odd, there are integerskandlwithaD 2kC1 andbD2lC1 Thus a 2 b 2 D.2kC1/ 2 2lC1/ 2

Thusa 2 b 2 is divisible by 4 but that is not enough to also say it is divisible by 8. Factoring the above equation gives: a 2 b 2 D4.k.kC1//4.l.lC1//: (1.2.1)

Using the insight that \( k(k+1) \) and \( l(l+1) \) are consecutive integers, we can conclude that both must be even This allows us to express \( k(k+1) = 2r \) and \( l(l+1) = 2s \) for integers \( r \) and \( s \) Substituting these expressions into the equation \( a^2 + b^2 = 8r8s = 8(rs) \) shows that \( a^2 + b^2 \) is divisible by 8.

Effective problem-solving involves multiple steps, as demonstrated in our example It begins with understanding key concepts, such as the definition of odd numbers, followed by algebraic manipulations Recognizing that we are not finished until we check for divisibility by 4 is crucial Further algebra reveals that we are working with two consecutive integers, which results in an even product This layered approach, combining insights with routine computations, enhances understanding and leads to a comprehensive solution Simple answers lack depth; it's the intricate process that fosters true insight.

Example 6 Letn2Nand suppose thatnis odd Prove that

Solution Sincenis odd, it is of the formnD2lC1for somel2Z The integer on the right-hand of the assertion becomes

The two numbers on the right are consecutive integers, and according to Problem 3 of Problem Set 1.1, their product is even, represented as 2k, where k is an integer This leads us to define k through the given equation.

.l 2 ClC3/.l 2 ClC4/D2k; we see that

Exercise 5 Letn2Nand suppose thatnis odd Prove that

Exercise 6 Letn2Nand supposenis odd Prove that

We now use Exercises1and2to solve some divisibility problems.

Example 7 Ifa; bandcare integers such thataj.bCc/andaj.bc/, thenaj2b andaj2c.

Solution Exercise1shows thatamust divide both the sum of.bCc/and.bc/ and their difference Thereforeaj2bandaj2c //

Example 8 introduces a problem utilizing Exercises 1 and 2, where the division of two integers leads to the division of both their sum and difference This technique is particularly effective because any integer divides itself For instance, if 3n8 is an integer, then 3n8/j and 3n8 will also divide any multiple of 3n8 Notably, 3n8/j divides 2 and consequently 3n8/j divides the integer 25, which lacks n as a factor This clever observation allows us to effectively solve Example 8.

Example 8 Find all values ofnsuch that bothnand2nC3

Any integer divides itself, which means that \(3n^8\) divides \(3n^8\) and \(2n + 3\) by assumption Using Exercise 2B with \(k = 3\) and \(l = 2\), we can determine that \(3n^8\) divides \(3(2n + 3)^2\), resulting in \(25\) If \(3n^8\) divides \(25\), then \(3n^8\) must equal \(1\), \(5\), or \(25\) Since \(2n + 3\) is a positive integer, this restricts the possible values of \(3n^8\).

3n8D C1;C5; or C25 so3nmust be 9, 13, or 33 ornD3, 13 3 or11.

Becausenis a positive integer by assumption, the only possibilities left arenD3 or11and they both work //

Here is an alternative solution of Example8which doesn’t use Exercise2B Let’s definemas

Then2nC3Dm.3n8/or3D3mn2n8m.

To aid in the factoring process, we multiply the last equation by 3 and adding 16 to both sides gives

The right-hand side of the equation simplifies to 0.3n^8/0.3m^2, indicating that 0.3n^8/0.3m^2 shares the same divisors as 25 The potential integer solutions are outlined in the following table.

(This means, for example, that3n8D 1, and3m2 D25is one possibility to check out) Examining each possibility gives:

Since bothnandmare assumed to be positive integers, there are only two solutions remaining

.nD3andmD9/or.nD11andmD1/:

In other words,nD3or11are only solutions (as before).

Note: Example8can also be solved in the following simple way Since 2nC3 3n8 2N then 6nC9 3n8 D2C 3n8 25 2N Then 3n8 25 2N, hence3n8D1,5, or25which gives nD3,11, or 13 3 ThusnD3or11are the only solutions inN.

Exercise 7 Letnbe a non-negative integer Find allnsuch that.2n1/j.6nC5/.

Examining this example through two different approaches highlights how a result like Exercise 2B can streamline proofs Although the second method used in Example 8 is straightforward, it relies on certain "tricks" to reach a conclusion Proving Exercise 2B provides a structured foundation for analyzing this example and facilitates the proof of additional results Problem-solving can involve either "tricks" or mathematical structures—both approaches are valid, ultimately depending on personal preference.

The allure of mathematics lies not only in the cleverness of its proofs and solutions but also in its coherence and foundational structure Each individual's perception of mathematical beauty is unique, reflecting personal interpretations of its elegance and interconnectedness.

For any odd integer \( n \), the sum of \( n \) consecutive numbers is divisible by \( n \) To demonstrate this, let \( x \) represent the first number in the sequence, and the sum can be expressed as \( x + (x+1) + (x+2) + \ldots + (x+n-1) \) This simplifies to \( nx + \frac{n(n-1)}{2} \), which is divisible by \( n \) However, this property does not hold true for even integers \( n \geq 3 \), as the sum of any \( n \) consecutive numbers in this case does not guarantee divisibility by \( n \).

3 Find allx2Zsuch that.3xC1/j.5x2/.

4 Assume thatnis an integer greater than 1 For what valuesnis 2nC1 n1 an integer?

5 Find all positive integersaandbsuch thatab Da5bC20 (Hint: What is aC5/.b1/?)

6 (a) Find all positive integersaandbsuch thataba3bD4.

(b) Find all positive integersaandbsuch thata.bC2/Db.

7 (a) Letm2Z Ifmj.21nC20/andmj.7nC3/for somen2Z, what are the possible value(s) ofm?

(b) Letb2Zand assumebj.bC8/,.b1/j.bC11/and.b4/j.3bC6/. Find the value ofb.

8 Using Exercise 2B, find all positive integers n such that 2nC3 4n1 is a positive integer.

9 Using the method of the alternate solution from Example8and the simple way described in the note following Example8, find all positive integersnsuch that

10 Using the method of the alternate solution from Example8and the simple way described in the note following Example8, find all positive integersnsuch that

11 Use all methods to find all possible positive integersn such that 2nC8 n7 is a positive integer.

12 Use all methods (similar to those above) to find all positive integersnsuch that

13 Leta, b,c,d,eandk be any integers If edivides.ka b/ande divides.kcd /, prove thatedivides.adbc/.

Long Division: The Division Algorithm

Long division is a fundamental concept in mathematics that you will encounter frequently, especially in teaching Mastering the procedural aspects of long division is essential, but developing a conceptual understanding is equally important Many number theory problems rely on a deep comprehension of long division For instance, when dividing 37 by 7, the quotient is 5, and the remainder is 2, illustrating the process of long division using variables a, b, q, and r.

Ifaandbare integers, witha > bandbpositive, doing what is usually called

Long division is a method used to determine how many times one integer can be subtracted from another The process begins with the integer 'a' and involves repeatedly subtracting 'b' from 'a' until reaching a point where 'a' is less than 'b' or the remainder is less than 'b' but greater than zero For example, when dividing 37 by 7, we subtract 7 from 37 multiple times, resulting in a quotient of 5 and a remainder of 2 This procedure is formalized in the Division Algorithm, a fundamental concept in mathematics.

The Division Algorithm Leta2Z,b2N, then there exist integersqandrsuch that aDqbCrand0r < b: ()

Furthermore, the integersqandrwhich solve Eq () are uniquely determined.

Definition The integerqin Division Algorithm () is called theQUOTIENTofaby bandris called theREMAINDERofaon division byb Note thatbjaexactly when the remainder ofabybis zero We sayais theDIVIDENDandbis theDIVISOR.

The Division Algorithm can be better described as the "successive subtraction" algorithm, particularly in the context of its application to bD7 and a D37, as illustrated in its preliminary sketch This terminology emphasizes the method's reliance on repeated subtraction when a is greater than zero.

Algorithm The first three problems of Problem Set 1.3 show the “successive subtraction” approach fora > 0.

To analyze the sum and product of two integers, n1 and n2, we consider their remainders when divided by b According to the Division Algorithm, if n1 can be expressed as n1 = q1b + r1, where 0 ≤ r1 < b, and n2 as n2 = q2b + r2, where 0 ≤ r2 < b, then the sum n1 + n2 can be represented as n1 + n2 = (q1 + q2)b + (r1 + r2) Similarly, the product n1 * n2 is expressed as n1 * n2 = q1q2b^2 + (q1r2 + q2r1)b + r1r2 These formulations highlight the relationship between the integers and their remainders in modular arithmetic.

The initial term of equation (1.3.1) is divisible by \( b \), and the first two terms of equation (1.3.2) are also divisible by \( b \) Consequently, this leads us to a valuable conclusion presented in the following proposition.

Proposition 2 Ifn 1 andn 2 are positive integers whose remainders on division by the positive integerbarer 1 andr 2 respectively, then

.n 1 Cn 2 /has the same remainder on division bybas.r 1 Cr 2 /has (1.3.3) and n 1 n 2 has the same remainder on division bybasr 1 r 2 has: (1.3.4)

Proof The Division Algorithm shows that there are unique integersq 1 ,q 2 ,r 1 , and r 2 such that ni DqibCri with0ri < bforiD1; 2: (1.3.5)

We first prove Eq (1.3.3) by adding the equations of (1.3.5) to obtain n1Cn2D.q1Cq2/bC.r1Cr2/: (1.3.6)

The Division Algorithm can be applied to the integer \( r_1 + r_2 \) When dividing \( r_1 + r_2 \) by \( b \), we can express the quotient as \( q \) and the remainder as \( r_1 + r_2 \) modulo \( b \), resulting in the equation \( r_1 + r_2 = q \cdot b + r \) where \( 0 \leq r < b \).

Equation (1.3.8) represents the integer \( n_1C n_2 \) as the sum of an integer multiple of \( b \) plus a remainder \( r \), where \( 0 \leq r < b \) This indicates that the quotient of \( n_1C n_2 \) when divided by \( b \) is \( q_1 + q_2 + q \), and the remainder \( r \) aligns with the definition provided in Equation (1.3.7), which describes the remainder of \( r_1 + r_2 \) upon division by \( b \).

To prove Eq (1.3.4) we follow the same procedure. n1n2Dq1q2b 2 C.q1r1Cq2r2/bCr1r2: (1.3.9) However, ifr Dremainder ofr1r2on division bybandqis its quotient, then r1r2DqbCrwhere0r < b:

Substituting into Eq (1.3.9) yields n1n2 D.q1q2bCq1r2Cq2r1Cq/bCrwith0r < b:

Thus, by uniqueness,rmust be the remainder ofn1n2on division byb Of course, q1q2bCq1r2Cq2r1Cqis the quotient ofn1n2byb, but that result is not useful.

In Eq (1.3.3), we did not assert that the remainder of n1Cn2 is always equal to r1Cr2 because the Division Algorithm indicates that the remainders depend on the specific values of n1 and n2 For instance, if n1 = 5 and n2 = 3, the combination n1Cn2 yields a different remainder than if n1 = 3 and n2 = 5, illustrating that the relationship is not universally applicable.

B Explain why in Eq (1.3.4) we did not claim that the remainder of n1n2/is alwaysr1r2 (Give an example.)

Example 9 Find the remainder of lD1841C1954 on division by 6.

Solution Since 1841 D 306/6C5 and1954 D 325/6C4, the remainder of lD3; 795on division by 6 therefore is the same as the remainder of (5 + 4) = 9 by

6 The answer is 3; that is, the remainder of 3795 on division by 6 is 3 This problem gives an example of why the remainder of.n 1 Cn 2 /is notr 1 Cr 2 //

Example 10 Find the remainder ofnD.1841/.1954/on division by 5.

Solution Since 1841 = 1840 + 1, the remainder of 1841 on division by 5 is 1 The remainder of 1954 = 1950 + 4 is 4, so Proposition2says that the remainder of their productn, is the product of.4/.1/D4(since4 < 5) //

Example 11 Find (a) the remainder of n D 40/ 5 on division by 19; (b) the remainder ofnD.40/ 10 on division by 19.

When dividing 40 by 19, the remainder is 2 By applying Proposition 2 repeatedly, we find that the remainder of 40 divided by 5, when divided by 19, is equivalent to the remainder of 25 divided by 19, which results in 13.

When dividing 40 by 19, the remainder is 2 Consequently, the remainder of \( \frac{40}{10} \) when divided by 19 is equivalent to the remainder of \( \frac{2 \cdot 5}{2} \) by 19 From part (a), we know that the remainder of \( 2 \cdot 5 \) by 19 is 13 Therefore, we need to calculate the remainder of \( \frac{13}{2} \) which equals 169 when divided by 19 Since 169 can be expressed as \( 19 \cdot 8 + 17 \), the final answer is 17 This example illustrates that the remainder of \( n_1 \cdot n_2 \) does not necessarily equal \( r_1 \cdot r_2 \).

The Division Algorithm typically assumes a positive divisor, but it can still be applied when the dividend is negative To understand this interpretation, let's consider an example where the dividend is less than zero.

Example 12 What is the quotient and remainder of5on division by 2?

Solution The precise conclusion of the Division Algorithm means that we must findq2Zandr2N[ f0gwith

In the case where both a and b are positive, we initially subtracted b from a; however, subtracting 2 from 5 results in 7, indicating an incorrect approach to finding the quotient and remainder of 5 when divided by 2 Instead, using addition will yield the correct results.

5CbD 3but3is not between 0 and 2 (1.3.11)

3CbD 1but1is not between 0 and 2 (1.3.12)

How many additions were there? There were 3 so we are led toqD 3andrD1. Putting these values forqandrinto Eq (1.3.10) gives

5D.3/2C1 which checks Thus the remainder is 1 and the quotient is3 Note that there is no assumption that the quotient must be positive in the Division Algorithm //

1 (a) What are the quotient and remainder of 63 divided by 17?

To solve the problem, begin by subtracting 17 from 63 repeatedly until the result is a non-negative integer less than 17 This process illustrates that the total number of subtractions performed corresponds to the quotient of 63 divided by 17, while the final result represents the remainder, which will be a number between 0 and 17.

2 (a) What are the quotient and remainder of 35 by 7?

(b) Repeat part b of Problem1above.

3 (a) With the help of Example12, what are the quotient and remainder of27 by 6?

(b) Repeat part b of Problem1above.

4 (a) What are the quotient and remainder of7divided by 3?

(b) What happens if you try to interpret the quotient of 7 by 3 using successive subtractions?

(c) What happens if you try to interpret the quotient of 7 by 3 using successive additions?

(b) What happens if you try to interpret the quotient of 5 by 3 using successive subtractions?

(b) What happens if you try to interpret the quotient of32by using successive subtractions?

(a) find the remainder of.12345/.678/on division by 13.

(b) find the remainder of.30/ 9 on division by 13.

8 Find the remainder ofnD.12345/.678/C30 9 on division by 13.

(a) find the remainder of.15743/.365/on division by 7.

(b) find the remainder of.50/ 15 on division by 49.

12 Suppose thaty is the sum of squares ofthreeconsecutive integers Prove that the remainder ofyon division bythreeis 2.

13 Suppose thaty is the sum of squares of anyfourconsecutive integers Prove that the remainder ofyon division byfouris 2.

14 (a) Given the results of Problems12and13, do you think it is reasonable to make the following conclusion?

Conclusion Letybe the sum of squares ofnconsecutive integers (n > 2). Then the remainder ofyon division bynis 2.

(The answer to this question is yes or no! That is, yes, it sounds reasonable or no, it doesn’t sound reasonable.)

(b) Is the above conjecture true? If so then prove it, otherwise find a counterex- ample (Hint: TrynD5.)

Fact 1 : There is a formula due to Jakob Bernoulli (1654–1705) that gives the sum of squares Ifn2is an integer then

15 Supposey is the sum of the squares ofnconsecutive integersn 2andxis the first integer.

(a) Show that yDnx 2 Cn.n1/xC n.n1/.2n1/

Hint: Use Bernoulli’s formula of Problem14for the sum of squares above. (b) Show that the remainder ofy on division bynis the remainder ofr D n.n1/.2n1/

6 on division by n(for example,n D 4 givesr D 14, so the remainder ofyon division bynis 2).

(c) Can you conclude from the formula (a) thaty is divisible by n? Why or why not?

Tests for Divisibility in Base Ten

The problem of divisibility involves determining whether a specific small integer can divide a larger integer, denoted as n This class of problems highlights the importance of problem-solving techniques in mathematics.

Mathematical induction serves as a fundamental approach for directly solving problems, particularly in the context of divisibility In this section, we will define key concepts and address the problem of divisibility by all integers up to 13.

Divisibility Problem Overview How can we determine when an integerkdivides another integern? What properties ofnguarantee thatkdividesn?

To determine divisibility by various small integers, we can analyze the combinations of digits in the base ten representation of numbers This approach allows us to establish clear criteria for identifying whether an integer is divisible by specific values.

This article explores tests for divisibility by various integers, specifically k values of 2, 3, 4, 5, 7, 8, 9, 11, 13, and all powers of 2 and 5 The tests utilize the sum and difference of digits in the base ten representation of numbers Notably, for k equal to 1, any integer n is divisible, while for k equal to 6, the tests for 2 and 3 can be applied Additionally, an integer is divisible by 10 if its last digit is zero The article emphasizes that to establish divisibility by composite numbers, it is sufficient to verify divisibility by their prime factors.

The base ten representation of an integer \( n \) consists of a collection of digits \( a_0, a_1, \ldots, a_l \), where each digit ranges from zero to nine Informally, \( n \) can be expressed as \( n = a_l a_{l-1} a_{l-2} \ldots a_1 a_0 \), with \( a_0 \) identified as the last digit of \( n \) Formally, this representation is defined by the equation \( n = a_l \cdot 10^l + a_{l-1} \cdot 10^{l-1} + \ldots + a_1 \cdot 10^1 + a_0 \), where all \( a_i \) are non-negative integers.

The following tests are labeled by the integer expected to divide the specified number With the exception of Test 2, each test is accompanied by an example prior to its proof During the proof, we will reiterate each test to clarify the notation used.

Test 2 A positive integernis divisible by 2 if and only if the last digit ofnis even.

In general,n2Nis divisible by2 k if and only if the lastkdigits ofnare divisible by2 k Equivalently, let the base 10 representation ofnben Dalal1: : : a0 Then

2 k jnif and only if2 k ja k1 : : : a0.

Exercise 9 Use Test 2 to decide if 1336 is divisible by 2 Is it divisible by 4? Is it divisible by 8?

Test 5 A positive integer is divisible by 5 if and only if the last digit is divisible by

5 (i.e the last digit is either 0 or 5) In general,n2Nis divisible by5 k if and only if the lastkdigits ofnare divisible by5 k

Example 13 Show that 375 is divisible by 5, 25, and 125.

Solution Since5D 5 1 ,25D 5 2 , and125D5 3 , we need to determine, thanks to Test 5, whether5j5,5 2 j75and5 3 j375, all of which are true Thus 375 is divisible by

Restatement of Test 5 If the base 10 representation ofnisnDa ` a`1 a 2 a 1 a 0 then5 k jnif and only if5 k jak1ak2 a 0

In this article, we will focus on the case when k equals 2, while leaving the cases for k equal to 1 and k equal to 3 as Exercise 10 The theorem states that 25 divides n if and only if 25 divides the integer represented by the expression a1a0, which can be expressed as 10a1 + a0 Additionally, when k equals 2, n can be represented as a`10` + Ca`110` + 1 + Ca2102 + (10a1 + a0) For readers familiar with mathematical induction, the general case can be proven using this method.

But every term in the first parenthesis has a factor of 100 Thus25jnif and only if25j.10a 1 Ca0/ Since10a1Ca0has as its base 10 representationa1a0, we are finished

Exercise 10 If the base 10 representation ofnisnDa`a`1 a2a1a0, prove that

A 5jnif and only if5ja 0 (Test 5 forkD1)

B 125jn if and only if 125 divides the integer whose base ten representation if a2a1a0 (Test 5 forkD3)

The upcoming three tests focus on analyzing the sums and differences of the digits that make up the number n in base 10 Before we begin these tests, it's essential to establish some terminology, as there is a small technical distinction based on whether n has an even or odd number of digits in its base ten representation.

Ifn2N, expressed as a base 10 number in the form nDalal1 a2a1a0, has a digit sum represented as Cal1C Ca2Ca1Ca0 For an even length l, the even digit sum is calculated as a0 + Ca2 + Ca4 + + Ca`2, while the odd digit sum is determined by a1 + Ca3 + Ca`3 + Ca`1.

When Ifl is odd, the even digit sum and odd digit sum are defined similarly, concluding with 1 and 1a respectively The even digit sum incorporates a0 along with other even-indexed digits, while the odd digit sum consists of a1 and the remaining odd-indexed digits.

Example 14 Ifn D3574then there are 4 digits in the base 10 representation ofn so that`D3 The digit sum is 19, the odd digit sum is 10, and the even digit sum is

9 IfmD3; 556; 143thenlD6and the even digit sum is3C5C1C3D12and the odd digit sum is5C6C4D15.

A positive integer is divisible by 3 if the sum of its digits is divisible by 3 Similarly, an integer is divisible by 9 if the sum of its digits is divisible by 9.

Example 14 (continued) Since the digit sum of n D 3574 is 19 and 19 is not divisible by 3, 3 does not divide 3574 Since the digit sum form D 3; 556; 143is

Restatement of Test 3/9 Letnbe represented asnD a ` a`1 a 2 a 1 a 0 Then we have the following two results:

A 3 dividesnif and only if 3 divides.a`Ca`1C Ca2Ca1Ca0/

B 9 dividesnif and only if 9 divides.a`Ca`1C Ca2Ca1Ca0/.

The proof for Part B will be left as an exercise, as it closely resembles that of Part A We will demonstrate that the remainder of a number \( n \) when divided by 3 is equivalent to the remainder of the sum of its digits when divided by 3 Notably, the remainder of 10 when divided by 3 is 1, and by Proposition 2, this means that the remainders of \( 10^2, 10^3, \) and so on, are also 1 Therefore, by using Equation (1.4.1) along with Equations (1.3.3) and (1.3.4), we establish that the remainder of \( n \) when divided by 3 is equal to the remainder of the sum of its digits.

.remainder of10 `1 /.remainder ofa`1/C C.remainder of10 2 /.remainder ofa2/

C.remainder of10/.remainder ofa 1 /Cremainder ofa 0 :

The initial term of each product in Equation (1.4.2) corresponds to the first statement in the proof, indicating that the remainder when divided by 3 is equivalent to the remainder of \( a^{C_1} C a_0 \) when divided by 3.

Included in the proof is the stronger result which we give as Corollary2.

A The remainder ofnon division by 3 is the same as the remainder of the digit sum ofnon division by 3.

B The remainder ofnon division by 9 is the same as the remainder of the digit sum ofnon division by 9.

Using Corollary2Bis also called the method of “casting out nines” Many grade school children are fascinated by this test.

Exercise 11 Find all values ofxin each of the following.

Test 11 A positive integernis divisible by 11 if and only if the difference between its even digit sum and odd digit sum is divisible by 11.

Example 15 LetnD 6853 Then the even digit sum is3C8D 11, the odd digit sum is5C6 D 11and the difference is1111 D 0 Because 11 divides 0, 11 divides 6853.

Remembering that zero is divisible by 11 (since110 D 0), do the following exercise Of course, zero is divisible by all integers except 0.

Exercise 12 Which of the following integers are divisible by 11?

We’ll restate Test 11 in the case where`is even When`is odd, the proof is the same—it is just the notation that is slightly different.

Restatement of Test 11 If the base 10 representation ofnisnDa`a`1 a2a1a0 then11jnif and only if

.a`Ca`2C Ca2Ca0/.a`1Ca`3C a3Ca1/

Proof We’ll use the simple observation that10D111with the obvious fact that we can rewrite Eq (1.4.1) as nDal.111/ l Cal1.111/ l1 C: : :Ca1.111/Ca0: (1.4.3)

Note that any power of.111/has 11 in each term except the last one which is ˙1(expand the term.111/ k using algebra without simplifying) More precisely, there are integersbk2Zwith

.111/ k D11.some integer/˙1D11bk˙1 whereC1is used ifkis even and1is used ifkis odd Whenlis even, for example,

Eq (1.4.3) becomes nDa l 11b l 1/ l Ca l 1.11bl11/ l1 C: : :Ca 1 11b 1 1/Ca 0 (1.4.4) or nD11.albl Cal 1bl 1C: : :Ca1b1/ C.a l al1C: : :Ca2a1Ca0/: (1.4.5)

A number \( n \) is divisible by 11 if and only if the alternating sum of its digits in base 10 is divisible by 11 This rule applies equally when \( l \) is odd, highlighting the consistent nature of this divisibility test To clarify its practical application, we emphasize the underlying definition demonstrated in this proof.

Definition TheALTERNATING DIGIT SUM OFnis the difference of the even digit sum and the odd digit sum.

Definition Suppose thatnDa l 10 l Cal110 l 1 C Ca 0 so thatnis written as a l al1 a 1 a 0 in base ten representation Consider theASSOCIATED SEQUENTIAL TRIPLE SUMforn; s T n/, defined as the finite sum: s T n/D.a0C10a1C10 2 a2/.a3C10a4C10 2 a5/

Let’s look at Example16A more closely to see a pattern which makes it much easier to follow the definition of the sequential triple sum In that case whenn D 176; 182; 461, writing vertically, s T n/D461 182 C176 455

To begin with the integer n, examine the three digits located between each comma and calculate their alternating sum This insight will prove beneficial as you tackle your homework assignments.

Test 7/Test 13 nis divisible by:

(a) 7 if and only ifs T n/is divisible by 7.

(b) 13 if and only ifs T n/is divisible by 13.

A Determine whethern D 176; 182; 461is divisible by 7, without the use of a calculator.

B For what values ofais nD14; 4a6; 3a2; 121 divisible by 13?

A The associated sequential triple sum fornis s T n/D.1C6.10/C4.100//

Since7j455, the originalnis divisible by 7 (The power of this method is that we’ve reduced the question of divisibility of a 9 digit number to that of a 3 digit number.)

B Once again, forming the associated sequential triple sum gives s T n/D121.3a2/C.4a6/14

Since 211 is not divisible by 13, there are no values ofafor which the givenn of Part B is divisible by 13.

Binary and Other Number Systems

Conversion Between Binary and Decimal

A systematic approach for converting between binary and decimal is beneficial, particularly using a method reminiscent of "synthetic division" or "Horner's Method" from high school algebra, which simplifies the process of converting binary numbers to decimal.

Example 19 Write.10111/2in decimal notation.

The calculation can be represented similarly to "synthetic division." In the accompanying table, we sum the numbers in each column, double the total, and then transfer that result to the next column.

Exercise 15 Write.10101/ 2 and.11110/ 2 in decimal notation.

Conversion from Decimal to Binary

Example 20 Write the base-10 number 45 in binary notation

Solution Take the highest power of 2 that is less than or equal to the given number,

45 This is 32 Write45 D 32C13 Take the highest power of 2 that is less than or equal to 13; this is 8 Write45 D 32C8C5 Repeat until we obtain 45 as a sum of powers of 2 Thus45 D 32C8C4C1 D 2 5 C2 3 C2 2 C2 0 Hence,

Alternative Solution There is a different method involving a repeated division algorithm which gives a different way of thinking of the solution to Example20.

Divide the previous quotient, 22, by 2 22D112C0

Stop when the previous quotient is 1

To convert a decimal number to binary, read the digits from bottom to top, starting with the last quotient followed by the remainder, resulting in 101101 in binary.

Exercise 16 A Write the base-ten number 451 in binary notation.

B Write the base-ten number 5001 in binary notation.

Arithmetic in Binary Systems

The operation in binary systems is essentially the same as in decimal systems We shall discuss addition, multiplication, subtraction, and division.

The addition in base-2 is constructed using the following facts.0C0D0,0C1D1,

1C0D1, and1C1D10(that is, write 0 and carry the 1) i.e.

This means we could say “1C1D10because we carry a 1” in base-2!

The rule for decimal multiplication also holds for the multiplication of binary numbers It is based on the following facts:00D0,01D0,10D0 11D1 i.e.

Solution We need to write out.101/ 2 101/ 2 Since.101/ 2 D2 2 C1,

Binary multiplication is performed using expanded notation in elementary mathematics This process can be simplified into a more concise method known as the final algorithm, which highlights the carrying from one column to the next in the multiplication process.

Subtraction in the Binary System

Recall that subtraction is the inverse operation of addition Therefore we have:0

0D0,10D1, and11D0,01D1(with borrowing 1 from the next column if possible) i.e.

(borrowing 1 from the next column).

Division in the Binary System

Division in base-2 will use the same long division procedure as we used in base-10.

Thus.11101/ 2 101/ 2 D.101/ 2 as quotient with remainder.100/ 2 //

Duodecimal Number System

Ifb D 12then the number system is called theDUODECIMALsystem Again the digits involved are elements of the setf0; 1; 2; 3; 4; 5; 6; 7; 8; 9; T; Eg In duodecimal,T denotes10andEdenotes11.

Conversion from Decimal to Duodecimal System

Dividenand each succeeding quotient by 12 until a zero quotient is obtained The sequence of remainders in reverse order yields the duodecimal representation ofn.

Example 27 Let n D 275 in base 10 What is the number of the duodecimal representative?

Example 28 Ifnis160in base 10, what is it in base 12?

Conversion from Duodecimal to Decimal System

Given an integernwith duodecimal representation nD.akak1: : : a0/12; its decimal representation can be obtained by computing nD12 k a k C12 k1 ak1C: : :C12 1 a 1 Ca 0 :

Exercise 21 Convert the following Decimal numbers to their Duodecimal equivalents and vice versa. i 523 ii 6,234 iii .2E4/ 12 iv .T 083/ 12

1 Convert the following Binary numbers to Duodecimal numbers and vice versa.

2 Complete the binary sums and difference without first converting to Decimal equivalents.

3 Complete the binary products and divisions without first converting to Decimal equivalents.

4 Another commonly used number system is the Hexadecimal system This system works in base 16 and uses the symbols f0; 1; : : : ; 8; 9; A; B; C; D; E; Fg:

(a) Convert the following Decimal numbers to their Hexadecimal equivalents and vice versa.

(b) Complete the Hexadecimal sums and differences without first converting to Decimal equivalents.

This chapter explores the structure of prime numbers through prime factorization and introduces key number theory tools such as greatest common divisors (GCD) and least common multiples (LCM) These concepts lay the groundwork for significant theorems, including the Fundamental Theorem of Arithmetic and the Euclidean Algorithm, along with its applications Additionally, the chapter addresses Diophantine equations, which focus on problems with integer solutions, and highlights their relevance in combinatorics.

GCD and LCM Through the Fundamental Theorem of Arithmetic

In this article, we explore the Fundamental Theorem of Arithmetic to determine the greatest common divisor (GCD) and least common multiple (LCM) of two integers We will begin by using unique prime factorization to calculate the GCD, followed by a definition of LCM along with three methods for its computation: prime factorization, its relationship with the GCD, and a familiar algorithm for GCD calculation This content is particularly relevant for future elementary and middle school teachers, as it aligns with the mathematics covered in introductory courses.

In this section, we explore the concept of divisibility by examining whether two integers, a and b, are both divisible by a common integer d Our focus is on identifying the largest integer that serves as a divisor for both a and b, which is referred to as the greatest common divisor (GCD).

GREATEST COMMON DIVISORofaandb It proves very useful in problem solving, showing that there are real numbers that aren’t fractions (are irrational.) © Springer International Publishing Switzerland 2015

R.S Millman et al., Problems and Proofs in Numbers and Algebra,

This section presents the formal definition of the concept and its initial applications Subsequently, we will explore the Division Algorithm, which leads to the efficient method known as the Euclidean Algorithm for determining the greatest common divisor of two numbers.

Definition Letaandbbe integers neither of which is zero Ifc 2 N,cdivides a andc dividesb then c is called a COMMON DIVISOR ofa andb A positive integer,d, is theGREATEST COMMON DIVISORofaandb, writtend DGCD.a; b/, provided that

2 ifcis any common divisor ofaandb, thencd.

Ifn2Zthen the set of positiveDIVISORSofnis the set of elements d.n/D fc2Njcdividesng:

Note that while a divisor ofnmay be negative, the greatest common positive divisor of two numbers must be positive by definition.

Example 31 What is the greatest common divisor of 24 and 60?

Solution We collect the positive divisors of 24 and 60 in the sets: d.24/D f1; 2; 3; 4; 6; 8; 12; 24g and d.60/D f1; 2; 3; 4; 5; 6; 10; 12; 15; 20; 30; 60g:

The positive common divisors of 24 and 60 is the set of elements in bothd.24/and d.60/; that is,d.24/\d.60/ Since d.24/\d.60/D f1; 2; 3; 4; 6; 12g and the largest common element of these is12, the GCD.24; 60/is 12 //

Exercise 22 Find the greatest common divisor of 36 and 118.

The way in which we found GCD.24; 30/is called themethod of exhaustion.

While this method may not be efficient for calculating the GCD of two numbers, such as 136 and 62, it demonstrates that every pair of numbers, a and b, has a greatest common divisor (GCD) By using the notation d(n) to represent the set of divisors of n, we observe that both d(a) and d(b) are finite sets that share the integer 1 Consequently, their intersection contains a largest element, which is the GCD of a and b, and is always at least 1.

1GCD.a; b/Dlargest element of.d.a/\d.b//minimumfjaj;jbjg:

2.1 GCD and LCM Through the Fundamental Theorem of Arithmetic 43

Let’s look again at Example31but see what happens if we use the Fundamental Theorem of Arithmetic to factor both 24 and 60 as the product of primes.

Example 32 Using prime factorization, find theGCD.24; 60/.

24D2 3 3and60D2 2 35 (2.1.1) where we have purposely written the primes in increasing order Looking at the prime factorization, Eq (2.1.1), we see that the largest integer which divides both is d D2 2 3D12DGCD.24; 60/:

Thus we have found theGCD.24; 60/by factoring both numbers into primes and then seeing which primes are in both the factorizations In this case, they are 2 and

In the analysis of primes, we identify the largest exponent for each prime number, such as 2 and 3, noting the exponent of 2 for prime 2 and 1 for prime 3 This method consistently applies, despite the increasing complexity of the notation, as demonstrated in Theorem 3.

Theorem 3 establishes a method for finding the greatest common divisor (GCD) of two positive integers, a and b, through prime factorization Let a be expressed as a = p1^s1 * * pk^sk and b as b = q1^r1 * * ql^rl, where p1, , pk and q1, , ql are the prime factors of a and b, respectively By rearranging the primes so that the first v factors are identical (p1 = q1, , pv = qv), the GCD(a, b) can be determined as GCD(a, b) = p1^t1 * * pv^tv, where ti represents the minimum of the corresponding exponents ri and si.

To show the theorem, we need the following lemma.

Lemma 1 Letn D p 1 n 1 p 2 n 2 p t n t withni > 0for eachi and letmbe a positive integer Thenmjnif and only ifmDp 1 m 1 p 2 m 2 p m t t withmi ni for eachi.

Proof IfmDp m 1 1 p m 2 2 p t m t withmi ni for eachi, then nDp 1 n 1 p t n t D.p n 1 1 m 1 p n t t m t /.p m 1 1 p t m t /: (2.1.2)

If \( n = mk \) for some integer \( k \), then the prime power decomposition of \( n \) is unique, leading to the conclusion that the prime power decompositions of \( m \) and \( k \) must align with that of \( n \) Consequently, we can express \( m \) and \( k \) in their prime power forms as \( m = p_1^{m_1} p_2^{m_2} \ldots p_t^{m_t} \) and \( k = p_1^{k_1} p_2^{k_2} \ldots p_t^{k_t} \), where \( m_i \) and \( k_i \) are non-negative integers Given that \( n = mk \), it follows that \( n_i = m_i + k_i \) and thus \( n_i \geq m_i \).

Now we are ready to prove Theorem3.

To demonstrate the relationship between two numbers \( a \) and \( b \), we can express them in terms of their prime factorizations: \( a = p_1^{s_1} p_2^{s_2} \ldots p_v^{s_v} \) and \( b = p_1^{r_1} p_2^{r_2} \ldots p_v^{r_v} \) The greatest common divisor (GCD) of \( a \) and \( b \) can be represented as \( \text{GCD}(a, b) = p_1^{t_1} p_2^{t_2} \ldots p_v^{t_v} \), where \( t_i \) is the minimum of \( r_i \) and \( s_i \) By defining \( d = p_1^{t_1} p_2^{t_2} \ldots p_v^{t_v} \), we establish that \( d \) divides both \( a \) and \( b \) If \( g \) is a common divisor of \( a \) and \( b \), it can also be expressed in terms of prime factors, leading to the conclusion that \( g \) must be less than or equal to \( d \) Thus, we confirm that \( d \) is indeed the GCD of \( a \) and \( b \).

Remark The above lemma provides an easy way to find all the positive divisors of a positive integer once its prime power decomposition is obtained.

Example 33 Find all positive divisors of 108.

Solution Since108D2 2 3 3 , the divisors of 108 are

Example 34 Find theGCD.504; 3675/using the prime factorization method.

Solution It is easy to find that

Thus, since the only primes that are in both numbers are 3 and 7 and each has exponent 1 in one of the numbers, the theorem says that

A prime number is defined as an integer greater than 1 that has no positive divisors other than itself and 1 Similarly, two integers are said to be coprime if their only common positive divisor is 1 This concept of coprimality will be crucial for the discussions in this book.

Definition The integersaandbareRELATIVELY PRIMEif the GCD.a; b/D1.

Being relatively prime is one extreme relationship for a pair of integers The next exercise is concerned with another extreme relationship.

Exercise 23 Ifa; b 2 Zand GCD.a; b/ D b, what is the relationship betweena andb? (Prove that your answer is correct.)

We now define rational and irrational numbers and apply the ideas above to show that thep

The concept of the greatest common divisor (GCD) can be applied to demonstrate the irrationality of certain numbers, such as prime numbers This serves as a prime example of problem-solving grounded in established mathematical principles.

Definition Ifxis a real number,xD r s wherer; s2Zands¤0, thenxis called aRATIONAL NUMBER We sayxis anIRRATIONAL NUMBERif it is not a rational number.

Proposition 3 (Reduction to Lowest Terms) Ifxis a non-zero rational number, thenxcan be written as xD a b; whereaandbare relatively prime integers: (2.1.4)

Proof Supposexis rational so thatx D r s forr; s2Z Letd DGCD.r; s/ Then xD r s D d r s d

If we letaD d r andbD d s then both are integers, sinced is a divisor of both and are relatively prime (why?) Thus, we have written the integerxas in Eq (2.1.4).

The ability to express any rational integer as the quotient of two relatively prime integers, often referred to as reducing to lowest terms, enables the use of proof by contradiction in mathematical arguments This approach is exemplified in various theorems, including Theorem 9 and the Rational Root Theorem (Theorem 20).

2is irrational, we will assume the opposite (i.e thatp

2is rational) and show that assumption leads to a contradiction and so is incorrect Since the assumption thatp

2is rational is false, it must be thatp

2is irrational, which is what we are trying to prove This technique is called “proof by contradiction”. Assume for the moment that thep

2is rational and so it is the quotient of two integers Thanks to (2.1.4), we may assume that p

2or a 2 D2b 2 (2.1.6) and soa 2 is even Ifawere odd (saya D 2`C1), its square (4` 2 C4`C1 D 2.2` 2 C2`/C1) would also be odd Therefore,ais even which means thataD2k for somek2N PuttingaD2kinto (2.1.6) yields

Thusb 2 , and henceb, is even by the same argument Since bothaandbare even, each is divisible by 2 Thus, GCD.a; b/ 2, which contradicts our assumption

[Eq (2.1.5)] and the proof is finished

In this section, we will briefly discuss the least common multiple (LCM) of two integers Although the greatest common divisor (GCD) will be more frequently referenced throughout this chapter, it is important to acknowledge the role of the LCM in elementary mathematics Both the GCD and LCM are fundamental concepts taught in schools.

Definition TheLEAST COMMON MULTIPLEof two integersaandb,LCM.a; b/, is the smallest positive integer that is a multiple of bothaandb.

We can recast this definition to be similar to the definition ofGCD.a; b/ by saying thatlDLCM.a; b/if

2 ifkis any other multiple ofaandbthenlk.

Ifn2Zthen thePOSITIVE MULTIPLESofnare collected in the set: m.n/D fc2Njndividescg:

TheLCM.a; b/is the smallest integer inm.a/\m.b/.

All elements of m.a/ and m.b/ are positive If both a and b are either positive or negative, then m.a/ and m.b/ will share at least the element ab Consequently, there exists a least common multiple (LCM) denoted as LCM(a, b), where m.a/ and m.b/ are less than or equal to this value.

Example 35 Find the least common multiple of 270 and 630.

Solution We will use the prime factorization of 270 and 630 to find the

LCM.270; 630/ It is easy to show that

Any multiple of both 270 and 630 must have in its prime factorization at least one 2, three 3s, one 5, and one 7 in it Thus, the smallest multiple of both numbers must be

This example illustrates the theorem analogous to Theorem 3, which employs prime factorization to determine the greatest common divisor (GCD) of two integers The primary challenge in proving this theorem lies in accurately managing the notation throughout the process.

Theorem 5 establishes a method for calculating the least common multiple (LCM) of two positive integers, a and b, through their unique prime factorization Let the prime factors of a be denoted as p1, p2, , pk, and those of b as q1, q2, , ql We express a as the product of its prime factors raised to their respective positive exponents, a = p1^s1 * * pk^sk, and b as b = q1^r1 * * ql^rl If the first v primes are shared between a and b (p1 = q1, , pv = qv), the LCM can be determined by taking the maximum exponent for each prime factor, specifically max(rj, sj) for j from 1 to v.

LCM.a; b/Dp 1 t 1 : : : p t v v p s vC1 vC1 : : : p s k k q vC1 r vC1 : : : q l r l :

We will not include a proof of the fact but ask the reader to supply one for a number of cases in which the notation is easier.

Proposition 4 Ifaandbare non-zero integers andd DGCD.a; b/then there are relatively prime integershandkwith aDdh andbDdk (2.1.7)

Proof Sinced is the GCD ofaandb,djaanddjb, so that there are integershand kwhich satisfy Eq (2.1.7) We will now show that, in fact,handkare relatively prime.

DefinerDGCD.h; k/ Ifr D1, then, by definition,handkare relatively prime and we are done Note that h r and k r are integers andaD.rd/ h r andbD.rd/ k r

If r > 1, then rd > d, rdja, and rdjb which is a contradiction sinced D GCD.a; b/ ThereforerD1, sohandkare relatively prime

Theorem 6 For any non-zero integersaandb,

Proof Let GCD.a; b/ D d Then there exist nonzero positive integers u andv whereaDduandbDdvandGCD.u; v/D1 Then we see thatLCM.a; b/Duvd and:

GCD.a; b/LCM.a; b/Dd.uvd/D.du/.dv/Dab:

Integers Modular n and Applications

Rational Roots of Polynomials

Định dạng
Số trang	230
Dung lượng	1,6 MB