Chapter 0 1-10

1.         For n = 5, 8, 12, 20, 25, find all positive integers less than n and relatively prime to n.

For numbers to be relatively prime, or coprime, the two numbers must have no common factors other than 1. So we have:

n = 5

1, 2, 3, 4

n = 8

1, 3, 5, 7

n = 12

1, 5, 7, 11

n = 20

1, 3, 7, 9, 11, 13, 17, 19

n = 25

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24

2.      Determine gcd(2^4*3^2*5*7^2, 2*3^3*7*11) and lcm(2^3*3^2*5, 2*3^3*7*11).

If we let c=gcd(a, b) we know c is the biggest number such that c divides a and c divides b.

So, gcd(2^4*3^2*5*7^2, 2*3^3*7*11) will be all numbers common between 2^4*3^2*5*7^2 and 2*3^3*7*11. We see the two numbers share 2^1, 3^2, and 7^1. Hence our answer is 2*3^2*7.

If we let d=lcm(2^3*3^2*5, 2*3^3*7*11) we know d must have one of each factor in the two numbers. So d = 2*3*5*7*11.

note: d is not 2*3*5*2*3*7*11 as we only need to take the distinct factors of each number. In essence, we do not want to double up on any numbers when finding lcm.

3.      Determine 51 mod 13, 342 mod 85, 62 mod 15, 10 mod 15, (82*73) mod 7, (51+68) mod 7, (35*24) mod 11, and (47+68) mod 11.

To find 51 mod 13, we may divide 51 by 13 and find there is a remainder of 12. You may also do it the hard way as I did at first and say 13 is too small +13=26+13=39+13=52 which is too big, so 51 mod 13 is 12.

(82*73) mod 7 is the same as (82 mod 7)*(73 mod 7).

(51+68) mod 7 is the same as (51 mod 7)+(68 mod 7).

4.      Find integers s and t such that 1=7*s+11*t. Show that s and t are not unique.

There exist more than one s and t such that 1=7*s+11*t. I found the answer through the wonderful guess and check method.

5.      In Florida, the fourth and fith digits from the end of a driver’s license number give the year of birth. The last three digits for a male with birth month m and birth date b are represented by 40(m-1)+b. For females the digits are 40(m-1)+b+500. Determine the dates of birth of people who have last five digits 42218 and 53953.

We see the last three digits of the first one are 218, so we see the person is male. If the person were female, the last three digits would be larger than 500. So we use the equation

40(m-1)+b=218

40m-40+b=218

40m+b=258

I trust in your ability to solve it from here. There are twelve months, so in the worst case scenario, you may try them each, starting with January.

We see the last three digits of the second one are greater than 500, so the person is a female. We use the equation 40(m-1)+b+500=953 and follow the same steps as above to arrive at the answer.

6.      For driver’s license numbers issued in New York prior to September 1992, the three digits preceding the last two of the number of a male with birth month m and birth date b are represented by 63m+2b. For females the digits are 63m+2b+1. Determine the dates of birth and sex(es)corresponding to the numbers 248 and 601.

Use the method from question 5 to solve this problem.

7.      Show that if a and b are positive integers, then ab=lcm(a, b)*gcd(a, b).

a and b are positive integers (given). Let a=p^m1*p^m2*…*p^mr and b=q^n1*q^n2*…q^ns where all ps are unique primes and all qs are unique primes. So we have both a and b broken down into primes.

Now, gcd(a, b) is the product of all ps and qs common between a and b. So if p^m1 were 2^4 and q^n3 were 2^7, gcd(a, b) would contain 2^4.

And the easiest way to find lcm(a, b) (that I could think of) would be to take a (you could take b and the outcome would be the same) and multiply a by every q which is not equal to some p in a.

Say for example we have 12 and 9. Lcm(12, 9) is 36. To find this we take the prime factors of 12 (2, 2, 3) and the prime factors of 9 (3, 3). To find lcm(12, 9) we take 9 and multiply it by the two 2s which are factors of 12. This gives us 36. Or we could take 12 and multiply by the one 3 which is “extra” in 9. This also gives us 36.

Now, when we look at the gcd(a, b) we see it is the product of all common prime factors, and lcm(a,b) would be (WLOG-without loss of generality) a times everything in b which is not also in a. With the two together we have everything in a and b, or ab.

8.      Suppose a and b are integers that divide the integer c. If a and b are relatively prime, show that ab divides c. Show by example, that if a and b are not relatively prime, then ab need not divide c.

We know by the problem that a and b are relatively prime. This means they share no common prime factors. We know from the above problem that to find the lcm(a, b) we take either a or b, let’s take a, and multiply by every factor of b which is not in a. This is every factor, so we have a*b. And as we just found the least common multiple, any common multiple will contain a and b.

9.      If a and b are integers and n is a positive integer, prove that a mod n=b mod n if and only if n divides a-b.

So, say we have the set {c, d, e, f, g, h, i, j, k}.

This was my first, not so good proof. It may help you understand the concept, but will not suffice as a real answer:

We shall begin with the case where a mod n = b mod n and prove that this implies a-b divides n. In the set above, let’s say a mod n = b mod n = f. This means that a is the same as b + some multiple of n which could be written as a=b+yn where y is some integer. Using algebra we can change this to a-b=yn. In other words, a-b is a multiple of n, which was what we wanted to prove.

My second proof is better.

We shall begin by writing a=q1n+r1 and b=q2n+r2. This comes from the division algorithm, and from it we also see that amodn=r1 and bmodn=r2 (Think of going through the set n times, and the remainder is what’s left over, giving you amodn). And we write a-b=q1n+r1-(q2n+r2). Algebra gives us a-b=n(q1-q2)+(r1-r2).

Now, for the first part we let amodn=bmodn and will prove this implies n divides a-b.

From above we know amodn=r1 and bmodn=r2. This means we have a-b=n(q1-q2)+(amodn-bmodn). Since amodn=bmodn we have a-b=n(q1-q2). We can let q1-q2=k where k is some integer and a-b=nk, so n divides a-b.

For the other direction we let n divide a-b and prove this implies amodn=bmodn.

If n divides a-b, we have a-b=nk for some integer k, and the remainder is 0. So this must mean the remainder, r1-r2=0, or r1=r2. And since we know amodn=r1 and bmodn=r2, amodn=bmodn.

Tada!

10.  Let a and b be integers and d=gcd(a, b). If a=da’ and b=db’, show that gcd(a’, b’)=1

The important thing for this problem is to make sure you are familiar with the theorems in the book. When I first attempted this problem, I thought I could do it on my own, but only after I went back and read the theorems did I realize how to solve the problem. Read the book—what a novel idea.

Also, if you do not solve this problem on your test, your professor will know you did not read the book. Reading the book is pretty crucial to difficult math classes, and failing to read implies a failing grade.

We will use Theorem 0.2 from page 5. This theorem states: For any nonzero integers a and b, there exist integers s and t such that gcd(a, b)=as+bt. Moreover, gcd(a, b) is the smallest positive integer of the form as+bt.

Now that we have read this, the problem comes down to simple algebra.

We have

d=as+bt for some integers s and t, and we can substitute a=da’ and b=db’ to get

d=da’s+db’t

d=d(a’s+b’t)

1=a’s+b’t

As seen from above, this is the exact form stated in the theorem (Let gcd(a’ b’)=d. Then d’=a’s+b’t.), so we know gcd(a’, b’)=1.

Tada!