Review Problems for the Final

Math 393

These problems are intended to help you study. The fact that a problem occurs here does not mean that there will be a similar problem on the test. And the absence of a problem from this review sheet does not mean that there won't be a problem of that kind on the test.

1. Find the coefficient of in the expansion of .

2. Find the number of elements of which are divisible by either 8 or by 22.

3. Prove that if , then .

4. Define

Prove that for ,

5. Let denote the Fibonacci number. Simplify to a single Fibonacci number, assuming that .

6. Find all integers such that .

7. Find and express it as an integer linear combination of 387 and 927.

8. Find all pairs of positive integers such that

9. (a) Explain why the Diophantine equation has no solutions.

(b) Solve the Diophantine equation .

10. Solve the Diophantine equation .

11. Find all integer solutions (positive or negative) to the Diophantine equation .

12. Use Fermat factorization to factor 43621.

13. Solve the system of congruences

14. Solve . Include ranges for the parameters which give all the distinct solutions mod 8, without duplication.

15. If n is an integer, can be divisible by 5?

16. Prove that if , , and , then .

17. (a) List the numbers in which are invertible mod 9.

(b) A number which is invertible mod n is a primitive root mod n if the powers u, , , ... of u give all the numbers which are invertible mod n. Show that 2 is a primitive root mod 9.

(c) Show by computation that there is no primitive root mod 8.

18. 2063 and 3041 are primes. Prove without computation that

19. Reduce mod 61 to a number in the range .

20. Solve the system of congruences

21. Compute , , and .

22. Calvin Butterball says: "If , the factors of n come in pairs , where . Hence, must be even." Is he right?

23. For what positive integers n does ?

24. Let . Consider the set S of integers in which are relatively prime to n. Prove that the sum of the elements of S is .

25. Find the last three digits of .

26. Show that if , then .

27. Prove that if n is an integer and , then is divisible by 54.

28. Show that has no prime factors less than 500.

29. Find the decoding transformation for the block cipher

30. Consider the exponential cipher which uses the prime and the exponent .

(a) Encipher the word FOOD.

(b) Find the deciphering transformation.

31. For an RSA cipher, it is known that the modulus is , and . Find the primes p and q such that .

32. Find all solutions to the congruence

Note: .

33. Find a solution to by lifting a solution to the congruence mod 17.

34. Suppose that p is an odd prime and . Compute .

35. Compute .

36. Compute .

37. Convert to base 10.

38. Convert 2781 to base 5.

39. Express 0.26 in base 5.

40. Find a decimal fraction in lowest terms equal to .

41. Express as a decimal fraction in lowest terms.

42. If b is an integer and , find a decimal fraction equal to .

43. Find the finite continued fraction expansion for .

44. (a) Find the first 5 convergents of .

(b) Find the exact value of .

45. Find the first 10 terms of the continued fraction expansion of .

46. (a) Find the continued fraction expansion of . Find the convergents , ..., .

(b) Use the convergents of the continued fraction expansion of to find a solution to the Fermat-Pell equation .

47. Find the convergents of the finite continued fraction .

48. Find the exact value of the periodic continued fraction .

49. Find the rational number in lowest terms with which best approximates .

Solutions to the Review Problems for the Final

1. Find the coefficient of in the expansion of .

I'll get a term by taking and . Thus, the coefficient is .

2. Find the number of elements of which are divisible by either 8 or by 22.

The number of elements of which are divisible by 8 is

The number of elements of which are divisible by 22 is

The number of elements of which are divisible by both 8 and 22 is the number divisible by their least common multiple, and . The number of elements of which are divisible by 88 is

The number divisible by both is counted in both the number divisible by 8 and the number divisible by 22. So it must be subtracted off once to get the number divisible by either 8 or 22:

3. Prove that if , then .

For , I have , and .

Suppose . I want to show that . Now

I know that by induction.

To show that , you can take several approaches. One approach is to consider mod 12 and show that you always get 0. A sneakier approach is to note that

In any event, since and , I have . This completes the induction step and the proof.

4. Define

Prove that for ,

For ,

The result is true for .

Let , and assume that the result holds for :

Then

(The second equality used the induction hypothesis, the third equality came from combining fractions over a common denominator, and the fourth equality came from the definition of the x's.)

Therefore, the result holds for n, so it's true for all , by induction.

5. Let denote the Fibonacci number. Simplify to a single Fibonacci number, assuming that .

6. Find all integers such that .

Suppose . Then

But , so .

Say , where . If , then

This is a contradiction. Hence, . This means that , so .

7. Find and express it as an integer linear combination of 387 and 927.

8. Find all pairs of positive integers such that

Note that . Hence,

Now 65 has 4 positive divisors: 1, 5, 13, and 65. I consider each of these cases.

Case 1. .

Using , I get . So

m and n are relatively prime ( ) positive integers whose product is 66. This gives me the following pairs (ignoring order):

Case 2. .

, so . Likewise, , so . Since I've divided m and n by their greatest common divisor, I must have .

Moreover,

So

a and b are relatively prime positive integers whose product is 14. This gives me the following pairs (ignoring order):

If , then multiplying by 5 gives .

If , then multiplying by 5 gives .

Case 3. .

, so . Likewise, , so . Since I've divided m and n by their greatest common divisor, I must have .

Moreover,

So

a and b are relatively prime positive integers whose product is 6. This gives me the following pairs (ignoring order):

If , then multiplying by 13 gives .

If , then multiplying by 13 gives .

Case 4. .

, so . Likewise, , so . Since I've divided m and n by their greatest common divisor, I must have .

Moreover,

So

a and b are relatively prime positive integers whose product is 2. The only solution (ignoring order) is .

If , then multiplying by 65 gives .

All together, the solutions are:

9. (a) Explain why the Diophantine equation has no solutions.

(b) Solve the Diophantine equation .

(a) If is a solution, then , but , contradicting the fact that .

(b) , so there are solutions.

I could find a particular solution by inspection; instead, I'll do it systematically using the Extended Euclidean algorithm.

Thus,

Multiply by 7:

Thus, , is a particular solution. The general solution is

10. Solve the Diophantine equation .

Rewrite the equation as

There are 4 possibilities, corresponding to the four ways of factoring 2 into a product of 2 integers.

Case 1: and .

Adding the equations gives , and so .

Case 2: and .

Adding the equations gives , and so .

Case 3: and .

Adding the equations gives , and so .

Case 4: and .

Adding the equations gives , and so .

The solutions are , , , and .

11. Find all integer solutions (positive or negative) to the Diophantine equation .

Note that and , so I can simply check cases. Note also that is even and 17 is odd, so must be odd, and hence x must be odd. Finally, if x works, so does , and likewise for y and . Therefore, I only need to check positive numbers.

Putting all these constraints together, I find that I only need to try and .

If , then , so . This gives the four solutions , , , .

If , then . This has no integer solutions.

The only solutions are , , , .

12. Use Fermat factorization to factor 43621.

Since , I'll start at .

I have

You can check that 241 and 181 are prime.

13. Solve the system of congruences

The moduli are relatively prime. The Chinese Remainder Theorem implies that there is a unique solution mod .

implies that . So

This means that , so

Then

This means that , so

Therefore, .

14. Solve . Include ranges for the parameters which give all the distinct solutions mod 8, without duplication.

Since , there are distinct solutions mod 8.

Write the congruence as the Diophantine equation

Let . Then

By inspection, , is a particular solution. The general solution is

Therefore,

By inspection, , is a particular solution. The general solution is

Reducing mod 8,

The parameter ranges , give the 8 distinct solutions:

15. If n is an integer, can be divisible by 5?

The table shows that for all n, . Therefore, is never divisible by 5.

16. Prove that if , , and , then .

means that and means that . Also, implies that

Multiply by :

and imply that . Also, and imply that .

Thus,

Hence, .

17. (a) List the numbers in which are invertible mod 9.

(b) A number which is invertible mod n is a primitive root mod n if the powers u, , , ... of u give all the numbers which are invertible mod n. Show that 2 is a primitive root mod 9.

(c) Show by computation that there is no primitive root mod 8.

(a) The numbers which are invertible mod 9 are those which are relatively prime to 9:

(b)

I've gotten all of the numbers in by taking powers of 2, so 2 is a primitive root mod 9.

(c) The numbers in which are invertible mod 8 are 1, 3, 5, and 7. However,

Therefore, you can't get all four of 1, 3, 5, and 7 by taking powers of any of these elements. Hence, there is no primitive root mod 8.

Note: If , then n has a primitive root if and only if , where p is an odd prime.

18. 2063 and 3041 are primes. Prove without computation that

By Fermat's theorem with the prime 3041,

By Fermat's theorem with the prime 2063,

Since 2063 and 3041 are distinct primes, they're relatively prime. Hence,

Remark: This result is true with any two distinct primes in place of 2063 and 3041.

19. Reduce mod 61 to a number in the range .

Since and , the numbers 5003, 5004, ..., 5062 must reduce mod 61 to 1, 2, ..., 60. By Wilson's theorem,

20. Solve the system of congruences

Write the system in matrix form:

Solve the system by inverting the coefficient matrix:

Note: You can also solve using Cramer's rule or row reduction. Or you can solve the second equation to get , and plug this into the first equation and solve for y.

21. Compute , , and

, so

22. Calvin Butterball says: "If , the factors of n come in pairs , where . Hence, must be even." Is he right?

Calvin is forgetting that a and b could be equal. In fact, is even provided that n is not a perfect square; otherwise, is odd. (Try writing a careful proof of this.) For example .

23. For what positive integers n does ?

If , then , so

On the other hand, suppose . I can write , where and . Then

Therefore, .

Hence, if and only if .

24. Let . Consider the set S of integers in which are relatively prime to n. Prove that the sum of the elements of S is .

The case can be proved directly: The only positive integer in relatively prime to 2 is 1, and .

So assume .

First, note that if , then . For

Thus, if and only if .

This means that the integers in S occur in pairs .

I claim that that the elements of such a pair are distinct. Suppose on the contrary that , so .

If n is odd, then is not an integer, but m is, and I have a contradiction.

If n is even, then is an integer that divides n (since ). Moreover, since , I have . This means that , so , another contradiction.

Thus, S can be broken down into pairs . The sum of the two elements in each pair is . Since , there must be pairs. Therefore, the sum of the elements of S is , as I wanted to show.

25. Find the last three digits of .

, so by Euler's theorem,

The last three digits of are 343.

26. Show that if , then .

Write the prime factorization of n:

Then

Here is a table of values of for various primes p:

Note that 36 does not occur in the first column, since is not prime. Clearly, the numbers in each row and column increase. Thus, any factors of 36 that could occur must be in the table.

The divisors of 36 that occur in the table are 3, 4, 6, 12, and 18.

18 can't be part of the factorization of , since I don't have any way of getting a factor of 2.

6 can't be part of the factorization, since I can only get the remaining factor of 6 as 6 or as . I can't use 6 a second time, and I can't get a factor of 2.

4 can't be part of the factorization, since I can only get the remaining factor of 9 as 9 or as . There is no 9 in the table, and I can't use 3 twice.

The only possibility is that ; consulting the table, this means that .

27. Prove that if n is an integer and , then is divisible by 54.

To say that is divisible by 54 is the same as saying that . Since and , it suffices to prove that and .

Since 2 is prime, by a corollary to Fermat's theorem.

, so . If , then , which contradicts the assumption that . Therefore, .

Hence, I may apply Euler's theorem: , so . Then

Since and , it follows that .

Note that the result may not hold if . For example, .

28. Convert to base 10.

Hence, .

29. Show that has no prime factors less than 500.

Since 31 is prime, divisors of have the form . I check numbers of this form less than 500:

Thus, has no prime factors less than 500. In fact, is prime.

30. Find the decoding transformation for the block cipher

The determinant of the coefficient matrix is , and . Hence, the matrix is invertible.

Hence, .

Therefore,

The decoding transformation is

31. Consider the exponential cipher which uses the prime and the exponent .

(a) Encipher the word FOOD.

(b) Find the deciphering transformation.

(a) Since , I use blocks of two letters. FOOD becomes 0514 1403.

I'll do the first block by way of example. I'll do the computation the way you would do it on a calculator which can't accomodate very big numbers.

Similarly,

The ciphertext is 1926\ 0592.

(b) I need d such that , i.e. such that . Use the Extended Euclidean algorithm:

Thus,

Thus, , and the decoding transformation is

32. For an RSA cipher, it is known that the modulus is , and . Find the primes p and q such that .

Note that

Thus,

Next,

Hence,

Then

33. Find all solutions to the congruence

Note: .

I'll begin by solving the congruence mod 7 and mod 29.

The solutions are obviously and .

The solutions are obviously and .

(In cases where you couldn't find solutions to these by inspection, you'd probably need to make a table of squares.)

Next, I combine solutions mod 7 with solutions mod 29 using the Chinese Remainder theorem.

First,

Hence, is another solution.

Next,

Note that I don't use and , because these are are negatives of the solutions I used first, so I'll just get 149 and 54 again.

Hence, is another solution.

All together, the solutions are .

34. Find a solution to by lifting a solution to the congruence mod 17.

Consider

Obviously, is a solution.

Method 1. Try to find a solution of the form to the original congruence:

I cancel the factor of 68, dividing the modulus by . This gives

So one solution is obtained by taking , which gives

Method 2. Use the algorithm given by the proof of the theorem on lifting solutions to polynomial congruences.

Let , so .

Note that .

Solve:

A solution to the original congruence is given by

The other solution is .

35. Suppose that p is an odd prime and . Compute .

First, .

Since , I may write . Then , so .

Similarly, . But shows that , so

Therefore, .

36. Compute .

Since ,

Therefore, .

37. Compute .

I'll use Jacobi symbols to simplify the computation:

38. Convert 2781 to base 5.

Thus, .

39. Express 0.26 in base 5.

Thus, .

40. Find a decimal fraction in lowest terms equal to .

Let . Then , so

41. Express as a decimal fraction in lowest terms.

Let . Then , so

Now

Hence,

42. If b is an integer and , find a decimal fraction equal to .

43. Find the finite continued fraction expansion for .

44. (a) Find the first 5 convergents of .

(b) Find the exact value of .

(a)

(b)

Therefore,

Thus,

This gives the roots

Since x is obviously positive, it follows that .

45. Find the first 10 terms of the continued fraction expansion of .

46. (a) Find the continued fraction expansion of . Find the convergents , ..., .

(b) Use the convergents of the continued fraction expansion of to find a solution to the Fermat-Pell equation .

(a) I'll use the recursion formula

Note that since is a quadratic irrational, I can stop once I see that the expansion has repeated.

Thus, . The convergents are

Note that , while .

(b) Since the period is 4, which is even, the numerator and denominator give a solution:

47. Find the convergents of the finite continued fraction .

48. Find the exact value of the periodic continued fraction .

Write , so

Let , so . Then

Clear the fraction to obtain a quadratic:

The solutions are

y must be positive, so

Hence,

49. Find the rational number in lowest terms with which best approximates .

I computed the first six convergents for the continued fraction expansion for . I conjecture that is the best rational approximation with denominator less than or equal to 50.

Suppose that is a better approximation, and . Then

Now , so

Hence,

Therefore, must be a convergent. However, the table shows that no convergent with denominator less than or equal to 50 approximates better than . Hence, there is no such , and is the best rational approximation with denominator less than or equal to 50.

The best thing for being sad is to learn something. - Merlyn, in T.H. White's The Once and Future King

Contact information