We revisited the first problem due today, the problem of whether there could be many primes which are "k mod n." You looked at this problem in a visual form by displaying the integers in n columns, then looking in column k. When you graph in 15 columns, for example, you find that the primes are segregated into columns 1,2,4,7,8,11,13,14. (A prime may occur at the top of a column that is otherwise empty, such as the prime 5, which occurs in column 5. This should not distract us from noting that the column is essentially empty, while the columns just named seem to have primes which go on forever.) A little experimentation confirms that the primes are found in columns k mod n where k is relatively prime to n, i.e., shares no common factors with n (except 1, of course, which is a factor of every integer).
Example: 15 and 16 are relatively prime, because 15=5*3 and 16=2*2*2*2. There are no common factors. (Note that 15 and 16 are relatively prime, as a pair, even though neither is prime.)
Example: 7 and 14 are not relatively prime. They have the factor 7 in common.
Example: 21 and 56 are not relatively prime. They have the factor 7 in common.
This notion of "relatively prime" is a very useful one, and we have already seen one example of how it controls the behavior of integers. We will see many more. Another way to think of the concept is to say that two numbers a and b are relatively prime if their greatest common divisor is 1, or, in more mathematical-looking notation, gcd(a,b)=1. This is clearly the same thing we said before, because any divisor of both a and b is a common factor. If it is greater than 1, then a and b are not relatively prime, because they share this factor. But if the greatest common divisor is 1, then they have no common factor greater than 1, and hence are relatively prime.
It is not at all necessary to factor a and b to determine if they are relatively prime. There is a very fast algorithm, called the Euclidean algorithm, to determine gcd(a,b) (the greatest common divisor of a and b). If it comes out 1, then a and b are relatively prime, otherwise they are not. Here it is:
(1) Let a>b>0, i.e., call a the greater of the two numbers. Try dividing b into a. If it goes in evenly, there is a remainder r=0. Otherwise there is some remainder r>0.
(2) If r=0, then gcd(a,b)=b. Otherwise gcd(a,b)=gcd(b,r). That is, the problem reduces to a new problem with smaller numbers. You can go back to step 1, replacing a by b, and b by r.
This algorithm terminates in a finite number of steps because the remainders r decrease by at least 1 at each step, and so must eventually become 0.
Example: gcd(56,21). Dividing 21 into 56 we find 2 with remainder r=14. So we find gcd(21,14). Dividing 14 into 21 we find 1 with remainder r=7. So we find gcd(14,7). Dividing 7 into 14 we find 2 with remainder r=0. Thus gcd(56,21)=7. (We had already noticed this above).
Example: gcd(409,357). Dividing 357 into 409 we find 1 with remainder 52. So we find gcd(357,52). Dividing 52 into 357 we find 6 with remainder 45. So we find gcd(52,45). Dividing 45 into 52 we find 1 with remainder 7. So we find gcd(45,7). Dividing 7 into 45 we find 6 with remainder 3. So we find gcd(7,3). Dividing 3 into 7 we find 2 with remainder 1. Thus the gcd(409,357)=1, i.e., 409 and 357 are relatively prime.
Example: gcd(2077,589). Dividing 589 into 2077 we find 3 with remainder 310. So we find gcd(589,310). Dividing 310 into 589 we find 1 with remainder 279. So we find gcd(310,279). Dividing 279 into 310 we find 1 with remainder 31. So we find gcd(279,31). Dividing 31 into 279 we find 9 with remainder 0. So gcd(2077,589)=31.
Find the following gcd's:
gcd(4042, 2193)
gcd(4757, 2911)
gcd(1541, 943)
4th one of your own choice, different from everybody else's! Make it two 4-digit numbers, chosen at random, and show all your work in the Euclidean algorithm to determine the gcd.