Relatively PrimeDate: 10/07/1999 at 02:23:38 From: Renee Dingus Subject: Relative prime number I am homeschooling my 13-year-old and we have come to factoring. It defines a relative prime number as "if 2 numbers have a greatest common factor of one, after prime factorization, it is a relative prime number." My daughter and I just don't understand. Would you be able to explain this to us in a more detailed fashion? Date: 10/07/1999 at 05:13:11 From: Doctor Joe Subject: Re: Relative prime number Dear Renee, We shall look at some definitions. (a) Factor Let x and y be two integers (whole numbers). We say that x is a factor of y if y = kx for some integer k. We may also say x divides y. If this sounds a bit abstract, let's look at a few examples: Example 1: 2 is a factor of 6 since 6 = 3 x 2. Example 2: 3 is a factor of 18 since 18 = 6 x 3. Example 3: 18 is a factor of 36 since 36 = 2 x 18. It is also good to look at some non-examples: Example 4: 6 is not a factor of 11 since 11 leaves a remainder of 5 when divided by 6. Example 5: 9 is a factor of 18 but not 14. From these examples, one can see that x is a factor of y if and only if y leaves no remainder when divided by x. (b) Prime Numbers The study of prime numbers has always been at the core of mathematics, especially the topic of number theory. A positive integer p (larger than 1) is called a prime number (or simply prime) if the only factors of p are 1 and p (itself). Let me make it clearer: Example 6: 2 is a prime number since 2 = 1 x 2. We see that the only integer divisors of 2 are 1 and 2. Example 7: 3, 5, 7, 11, 13, 17, 19, 23 are examples of primes. Example 8: 12 is not a prime number, as 12 = 3 x 4. So besides 1 and 12, the integers 3 and 4 are factors of 12. (c) Prime Factorization It is a renowned theorem in elementary number theory that a positive integer may be factored into primes in an essentially unique way. This is called the Fundamental Theorem of Arithmetic. What this means in a nutshell is: Say we pick the number 12. Then 12 = 2 x 2 x 3. But you may say that 12 = 2 x 3 x 2. However, if you re-order them, you still get 2 x 2 x 3. This is what I mean by "essentially" unique. I shall not prove this theorem, but what we discuss will depend on some knowledge of this. I am confident that you know how prime factorization of an integer is performed, so I shall not review with you the technicalities. (d) Relatively prime (the main topic of the discussion) Definition (Common Factor): The common factor of two integers x and y is an integer d such that d is a factor of both x and y. In other words, d divides x and d divides y. Example 9: 2 is a common factor of 4 and 6 since 4 = 2 x 2 and 6 = 3 x 2. Example 10: 12 is a common factor of 144 and 36. Example 11: 1 is the only common factor of 26 and 51. From example 11, we see that two integers may have no common factors other than the trivial factor 1. This is this case that motivates the definition that follows. Definition (Relative primes): Two integers are relative primes (or termed as relatively prime or as, in some more technical books, co-prime) if they have no common factor other than 1. Example 12: 26 and 51 are relative primes. Example 13: 81 and 343 are relative primes. Remarks: (a) Note that one cannot say that a particular number is a relative prime. So there is some fundamental error in the way you phrased your question. The word "relative" indicates that there is some form of comparison. It takes at two integers to get the definition going. (b) One can also say that 12, 121, 343 are relatively prime, as the only common factor of 12, 121 and 343 is 1. So the concept of relative primes is not just restricted to a comparison of 2 integers. Now the natural question is: How do I know whether two given integers are relative primes? To answer this question, we first take the naive approach (but this approach is important as it serves to clarify and internalize this concept.) 1) Naive Approach Say we have 2 integers: 24 and 77. The only way to check whether 24 and 77 are relative primes is to actually confirm that 1 is the only common factor of 24 and 77. All we need to do is to perform a prime factorization of 24 and 77 respectively: to list out all the prime divisors of 24 and 77, hoping that there is not even one common prime factor. This method would suffice. To set the picture clear: 24 = 2 x 2 x 2 x 3 = 2^3 x 3 77 = 7 x 11. As we can see, there is no prime number that divides both 24 and 77. Thus, the only factor of 24 and 77 is 1; in other words, 24 and 77 are relatively prime. You can try out a few examples: Example 14: 45 = 3 x 3 x 5 26 = 2 x 13 Therefore 45 and 26 are relative primes. Example 15: 34 = 2 x 17 99 = 3 x 3 x 11 Therefore 34 and 99 are relative primes. Example 16: 24 and 56 are not relative primes since 8 is a common factor of 24 and 56. (Of course, 2 is a common factor of 24 and 56. In fact this would suffice to conclude that 24 and 56 are not relative primes.) 2) Advanced Method Let's take 24 and 77. Take the larger of the two: 77. Divide this by the smaller of the two, i.e. 77 divided by 24. We can see that 77 leaves a remainder of 5 when divided by 24. This statement may be more precisely expressed as: 77 = (24)(3) + 5 ......................................[Eq. 1] Now we shall perform some sort of algorithm: Take 24 to be divided by 5 and check the remainder. This time the remainder is 4. 24 = (5)(4) + 4 .......................................[Eq. 2] We continue to take 5 to be divided by 4, and we obtain the remainder as 1. 5 = (4)(1) + 1 ........................................[Eq. 3] We continue to take 4 to be divided by 1, and we shall have no remainder: 4 = (1)(4) + 0 ........................................[Eq. 4] The list of remainders we obtained so far is: {5, 4, 1, 0} We note that the last non-zero remainder is 1. Theorem: If the last non-zero remainder is 1, then the two integers we started off with are relative primes. In this case, we can conclude that 24 and 77 are relative primes. Let's apply this method to check the relative primality of 56 and 89. 89 = (56)(1) + 33 56 = (33)(1) + 23 33 = (23)(1) + 10 23 = (10)(2) + 3 10 = (3)(3) + 1 3 = (3)(1) + 0 Since the last non-zero remainder is 1, 56 and 89 are relative primes. Note that this advanced method is indeed a general and efficient method, as it avoids the tedious task of factoring two integers (not to speak of seeking the common factors). It is extremely helpful whenever the two integers in question are large. However, for your 13- year-old daughter, this method is a bit advanced, so you may use it as a secret algorithm to check her answers to such questions. I hope what I have explained helps. Regards, Doctor Joe, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/