Review Sheet for Test 2

Math 393

These problems are provided to help you study. The presence of a problem on this handout does not imply that there will be a similar problem on the test. And the absence of a topic does not imply that it won't appear on the test.

1. Solve the congruence

2. Solve the congruence

3. Find all solutions to the congruence

4. Solve the system of congruences:

5. Find the smallest integer which leaves a remainder of 11 when divided by 13, leaves a remainder of 5 when divided by 8, and leaves a remainder of 7 when divided by 9.

6. Solve the system of congruences

(Note that the moduli aren't relatively prime, so you can't use the method of the Chinese Remainder Theorem proof. Solve directly using algebra instead.)

7. (a) Solve the congruence

(b) Solve the congruence

(c) Solve the congruence

8. Consider the system of congruences

Solve the system by:

(a) Using ordinary algebra.

(b) Inverting the coefficient matrix.

(c) Using Cramer's Rule.

9. Find the least positive residue of mod 13.

10. How many zeros does the decimal expansion of end in?

11. Reduce to a number in the range .

12. Reduce to a number in the range .

13. What is the remainder when is divided by 107?

14. Reduce to a number in the range . (Note: , and 107 and 109 are prime.)

15. Simplify to a number in the range .

16. For what prime numbers p does p divide ?

17. Solve .

18. (a) By making a table, find all solutions to

(b) For each solution you found in (a), generate a solution to

(Alternatively, show that this is not possible.)

19. Compute .

20. Suppose . How many positive factors does n have?

21. Suppose that . Prove that .

22. Reduce to a number in the range .

23. Prove that if , then .

24. Find the last three digits (units, tens, and hundreds) of .

25. Compute , , , and .

26. What positive integers have exactly three positive divisors?

27. Suppose that , where n is an odd number. Prove that m has no more than 5 different odd prime divisors.

28. Suppose that .

(a) Show that if p is a prime and , then .

(b) Show that the largest power of 3 that can divide n is .

(c) Show that .

29. Let n be the square of an odd integer. Prove that is odd.

30. Find all positive integers n such that .

31. For what integers is an odd number?

32. Let p be prime. Show that .

33. Give a set of infinitely many integers n such that .

34. Prove that if , then n is square-free --- that is, there is no prime p such that .

35. Find all positive integers n satisfying and .

36. In each case, if the function is multiplicative, prove it; if it is not, give a specific counterexample.

(a) given by

(b) given by

37. Let denote the divisor sum of the arithmetic function f. Suppose . Compute .

38. Find .

39. Find a proper factor of .

Solutions to the Review Sheet for Test 2

1. Solve the congruence

Add 6 to both sides (using the fact that :

I want a reciprocal of 6 mod 13. Note that . Express as a linear combination of 6 and 13:

Thus,

Now , so 11 is the reciprocal of 6 mod 13. Multiply both sides of the equation by 11, and reduce the right side:

2. Solve the congruence

Determine the parameter ranges which give the correct number of solutions mod 9.

Since , there are solutions mod 9.

Rewrite the equation as a Diophantine equation:

Set , so

, is a particular solution. The general solution is

Now

, is a particular solution. (I juggled the numbers: and . The point is that you can do the s-part and the number part independently.) The general solution is

Taking everything mod 9,

Note: It turns out that and will give 27 independent solutions.

There are indeed 27 distinct solutions mod 9, so those are all the solutions.

3. Find all solutions to the congruence

If , then , so . This does not give a solution.

Suppose that . By Fermat's Theorem, , so . The equation becomes

The solution is .

4. Solve the system of congruences:

The moduli 8, 5, and 7 are pairwise relatively prime, so there is a unique solution mod , by the Chinese Remainder Theorem.

You can solve the system using the formulas given in the proof of the Chinese Remainder Theorem, or you can solve the congruences iteratively, using basic algebra and modular arithmetic. I'll take the second approach, but the first approach is fine (provided that you can recall the formulas exactly).

First, means that

Substitute this in the second equation:

means that , so

Substitute this in the third equation:

means that , so

5. Find the smallest integer which leaves a remainder of 11 when divided by 13, leaves a remainder of 5 when divided by 8, and leaves a remainder of 7 when divided by 9.

The conditions in the problem are equivalent to the system of congruences

gives . Plugging this into the second congruence gives

The last congruence gives . Plugging this into , I get

Substituting this into the third congruence yields

The last congruence gives . Plugging this into , I get

6. Solve the system of congruences

Since , the system has solutions. Since the moduli are not relatively prime, I can't use the formulas in the Chinese Remainder Theorem. Instead, I'll use the algebraic approach.

gives . Plugging this into the second congruence, I get

I want to divide the 12's by 12. To do this, I must divide the modulus 18 by . I get

Plugging this into , I get

7. (a) Solve the congruence

(b) Solve the congruence

(c) Solve the congruence

(a) Since , the congruence has no solutions.

(b) Since , there are solutions. The congruence can be written as

If I cancel the common factor of 4, I must divide the modulus by . This gives

Since , multiplying by 2 yields

The original congruence was mod 10. The numbers in the set 0, 1, ... 9 which satisfy are 4 and 9. Therefore, the solution is or .

(c) One approach is to convert the congruence to a Diophantine equation. But since the modulus is prime, it's easier to regard the congruence as a system of congruences mod 11 which happens to have only one equation! I'll row reduce the augmented matrix to row-reduced echelon form:

(I multiplied by 4 because .) The last matrix says

Set . Then . The solution is

8. Consider the system of congruences

Solve the system by:

(a) Using ordinary algebra.

(b) Inverting the coefficient matrix.

(c) Using Cramer's Rule.

(a) Multiply the second equation by 4 and subtract it from the first equation to eliminate x:

Substitute this into and solve for x:

(b) The matrix form is

To solve the system by inverting the coeffient matrix, multiply both sides by the inverse of the coefficient matrix:

The solution is and .

(c) The matrix form is

I have

Notice that in the second and third determinants, I replaced the first and second columns, respectively, of the coefficient matrix by the constant matrix .

Note that . So by Cramer's Rule,

9. Find the least positive residue of mod 13.

First, , so .

Since , Fermat's Theorem gives . Since , I have

That is, .

10. How many zeros does the decimal expansion of end in?

The number of zeros that the decimal expansion of ends in is equal to the number of factors of 10 which divide .

Since and since 5 is greater than 2, the number of factors of 10 which divide is equal to the number of factors of 5 which divide . Now is the product of the numbers in . Factors of 5 come from three kinds of numbers in this set:

(a) Numbers divisible by 5 but not 25 contribute 1 factor of 5.

(b) Numbers divisible by 25 by not 125 contribute 2 factors of 5.

(c) Numbers divisible by 125 contribute 3 factors of 5.

(There are no numbers in the set divisible by the next power of 5, which is 625.)

The number of numbers in the set divisible by 5 is .

The numbers divisible by 25 contribute 2 factors of 5, but one of the contributions was counted when I counted the numbers divisible by 5. So I just count them once: There are .

Likewise, the numbers divisible by 125 contribute 3 factors of 5, but one of the contributions was counted when I counted the numbers divisible by 5, and another when I counted the numbers divisible by 25. So I just count them once: There are .

Hence, the total number of factors of 5, and the number of zeros in the decimal expansion, is .

11. Reduce to a number in the range .

Since 47 is prime and , by Fermat's theorem. Now

Hence,

12. Reduce to a number in the range .

89 is prime, and . By Fermat's theorem,

Hence,

By the Extended Euclidean algorithm, . So

13. What is the remainder when is divided by 107?

Note that 107 is prime. By Wilson's theorem,

Since ,

Therefore,

leaves a remainder of 53 when it's divided by 107.

14. Reduce to a number in the range .

Let . Then

Next,

Now gives . So

So

15. Simplify to a number in the range .

By Wilson's theorem, . So

It follows that , so

16. For what prime numbers p does p divide ?

Suppose , i.e. .

, so doesn't work.

Assume then that p is an odd prime. By Fermat's theorem, , so

This means that . The only odd prime which divides 3 is . Since , 3 works, and it's the only prime that works.

17. Solve .

Note that 19 is prime. By Fermat's theorem, for any x. Therefore, , and the equation becomes

This gives . Since 19 is prime, the only solutions are and .

18. (a) By making a table, find all solutions to

(b) For each solution you found in (a), generate a solution to

(Alternatively, show that this is not possible.)

(a)

The solution is .

(b) Let , so . Then

Note that . I have

Let

Then

This is a solution to .

19. Compute .

20. Suppose . How many positive factors does n have?

Since , it follows that n is prime. Hence, it has 2 positive factors, namely 1 and n.

21. Suppose that . Prove that .

Note that

By Euler's Theorem, .

22. Reduce to a number in the range .

Since , Euler's theorem implies that . Now

Hence,

23. Prove that if , then .

Note that

So applying Euler's theorem directly gives , which is not what I want.

Instead, I'll use the fact that if and and , then . Write . Since , I also have and .

I have

By Euler's theorem,

I have

By Euler's theorem,

Since and , the result I cited above shows that .

24. Find the last three digits (units, tens, and hundreds) of .

I need to find . Note that

Since , by Euler's Theorem,

Hence,

The last three digits are 913.

25. Compute , , , and .

Since ,

Since , .

Since ,

Since ,

26. What positive integers have exactly three positive divisors?

Suppose . Suppose the prime factorization of n is

Then

This is only possible if and . This gives . Therefore, .

Therefore, the positive integers which have exactly three positive divisors are squares of primes.

27. Suppose that , where n is an odd number. Prove that m has no more than 5 different odd prime divisors.

Suppose , where the p's are distinct odd primes and the r's are greater than 0. Then

Now

Since is odd, is even. Thus, each odd prime divisor of m contributes a factor of 2 to . But is the largest power of 2 which divides . Therefore, m can't have more than 5 different odd prime divisors.

28. Suppose that .

(a) Show that if p is a prime and , then .

(b) Show that the largest power of 3 that can divide n is .

(c) Show that .

(a) Suppose is the largest power of p which divides n, where . Suppose also that . Then

But , so , and this is impossible. Hence, if p is a prime and , then .

(b) Suppose is the largest power of 3 that divides n. Then

If , then , which is a contradiction. Hence, , and the largest power of 3 that can divide n is .

(c) Suppose that is the largest power of 7 that divides n. Then

This is a contradiction, since . Therefore, .

29. Let n be the square of an odd integer. Prove that is odd.

Let , where m is odd. Then n is odd, so the factors of n other than m occur in pairs a, b, where , , and a and b are odd. Hence, is even, and the sum of the factors of n other than m is a sum of even numbers. Therefore,

30. Find all positive integers n such that .

Suppose . I may assume , since . Thus, 1 and n are distinct divisors of n. Let d be the sum of the divisors of n other than 1 or n. Then

If the largest divisor in d is 6, then n is divisible by 2 and 3 as well. This gives , which is a contradiction.

If the largest divisor in d is 5, then , where s is the sum of the other terms in d. But then , and 1 can't be one of the divisors in d. This is a contradiction.

If the largest divisor in d is 4, then 2 is also a divisor of n. This is possible, since . In this case, the divisors of n are 1, 2, 4, and n, so . This works, since .

If the largest divisor in d is 3, then , where s is the sum of the other terms in d. But then , for which the only possibilities are 3 and . The first is ruled out, because 3 was already accounted for; the second is ruled out, because d does not include 1. Hence, this is a contradiction.

The largest divisor in d can't be 2, because there is no way to write 6 as a sum of 2 and integers less than 2 and bigger than 1.

Therefore, the only positive integer n such that is .

31. For what integers is an odd number?

First, is odd.

Factors of n come in pairs: . Each such pair contributes two factors, provided that . Hence, then number of factors must be even, unless for some a.

Thus, is odd exactly when n is a perfect square.

32. Let p be prime. Show that .

Hence, .

33. Give a set of infinitely many integers n such that .

If , then . Thus, all of the integers in the following set satisfy :

34. Prove that if , then n is square-free --- that is, there is no prime p such that .

Suppose that , but , where p is prime. Then

Since as well, I have .

However,

This is a contradiction. Hence, there is no prime p such that .

35. Find all positive integers n satisfying and .

Suppose that .

The formula for in terms of the prime factorization of n implies that if p is prime and , then .

First, if p is prime and , then , so . Hence, . Thus, n can only be divisible by primes from 2 through 19.

If , then , which is impossible for . Hence, .

If , then , which is impossible for . Hence, .

If , then , which is impossible for . Hence, .

If , then , which is impossible for . Hence, .

At this point, I may suppose that the prime factorization of n is

In this expression, a, b, and d may be zero, but I know that . So I have

Hence,

If , then , and . This is impossible, since the left side is equal to 3. Hence, .

If , then

This is impossible, since the left side is equal to 3. Hence, .

Now I have

Consequently,

If , then

This is impossible, since the left side of the previous equation is 3. Therefore, .

But now I have , and no will make this true.

Having ruled out all possibilities, I conclude that there are no positive integers n satisfying and .

36. In each case, if the function is multiplicative, prove it; if it is not, give a specific counterexample.

(a) given by

(b) given by

(a) , but

Hence, f is not multiplicative.

(b)

Hence, g is multiplicative --- in fact, completely multiplicative.

37. Let denote the divisor sum of the arithmetic function f. Suppose . Compute .

38. Find .

If a and b are positive integers, then

Thus,

39. Find a proper factor of .

A prime factor of must have the form .

233 is a proper factor of .

Change is not made without inconvenience, even from worse to better. - Richard Hooker

Contact information