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. Consider the set of integers

When the Well-Ordering Axiom is applied to S, it asserts the existence of a certain element of S. What is the element?

2. (a) Let S be the set of real numbers x such that , with the usual ordering. Is S well-ordered?

(b) Let S be the set of integers x such that , with the usual ordering. Is S well-ordered?

3. Compute , , and .

4. Compute the exact value of .

5. Compute the exact value of .

6. Simplify to a single binomial coefficient.

7. The Gamma function is defined by

Prove that if , then

Thus, the Gamma function satisfies the same kind of recursion relation as the factorial function.

8. Prove that if and , then

9. Find the coefficient of in the expansion of .

10. Find and express it as a linear combination of 3914 and 2442.

11. Calvin Butterball has two egg timers that he bought after watching an ad on TV. One timer rings exactly 8 minutes after it is started; the other rings exactly 15 minutes after it is started. While each timer is running, no information about the time it is keeping is available. How can Calvin use the timers to time a 4-minute egg?

12. Find the greatest common divisor and least common multiple of and .

13. The sum of two numbers is 2736. Their least common multiple is 77592. Find the numbers.

Note: This is a difficult problem; try it last, and if you get stuck, at least try to follow the solution.

14. (a) If x is an integer, can be prime?

(b) If x is a positive integer, can be prime?

(c) If x is an integer, can be prime?

15. Prove that if n is an integer and , then is not prime.

16. Prove that if leaves a remainder of 4 when it's divided by 5, then leaves a remainder of 3 when it's divided by 5.

17. Prove that the square of an integer does not leave a remainder of 2 when it's divided by 3.

18. Give three integers a, b, and c such that a does not divide either b or c, but a divides .

19. Let c, x, and y be integers, where . Prove that if and only if .

20. Calvin Butterball reasons that if , then and b must be relatively prime, because you've divided out of a all the factors that a and b had in common.

If he's right, prove it. If he's wrong, give a specific counterexample.

21. Suppose . What are the possible values of ?

22. Let n be a positive integer, and let x be an integer. Suppose that and . Prove that .

23. Prove that if and , then .

24. How many integers in the set are by either 3 or 7, but not by both?

25. How many integers in the set are divisible by 3 but not 7?

26. Prove that if and n divides both and , then .

27. Suppose that m and n are integers, and you know that

What are the possible values of ? Why?

28. Prove that if n is a positive integer of the form , then n must have a prime factor of that form.

29. Prove that if , then

30. Prove that if denotes the Fibonacci number (where and ), then

31. Let denote the Fibonacci number (where and ).

Prove that if , then

32. A sequence of integers is defined by

Prove that

33. Use induction to prove that for .

34. Let . Prove that

35. Let be a polynomial with integer coefficients, and let be the derivative. Prove that

Hint: Use induction on the degree of f. For the induction step, write

Let and apply the induction hypothesis to .

36. Let x, y, and z be positive integers, and suppose the products , , and are all perfect cubes. Prove that x, y, and z must be perfect cubes.

37. Suppose that p, q, and r are distinct prime numbers,

What are the possible values of y?

38. Suppose that the prime factorization of an integer n is

( , , and are distinct primes.)

Write n as a product of integers , where a is a perfect square
and b is * square-free* --- that is, b is not
divisible by the square of any positive integer except 1.

39. Find the prime factorization of 15400 by trial division.

40. Use Fermat factorization to factor 25877 into primes. (You should use Fermat factorization rather than some other method, and you should show the trial values.)

41. Find the general solution to the Diophantine equation

42. Find the general solution to the Diophantine equation

43. Find the general solution to the Diophantine equation

44. Bonzo buys some books that cost $7 each and some books that cost $15 each. The books cost a total of $349. What is the largest total number of books Bonzo could have bought?

45. I. M. Snarky buys 43 apples and oranges. The apples cost 10 cents more than the oranges, and he spends a total of $30.68. Find the number of each fruit that he bought and their prices.

46. Solve the following Diophantine equation by factoring:

47. Is prime?

48. Find .

49. Suppose that . Prove that if and , then .

50. Prove that if , then is not divisible by 5.

51. (a) Construct a table for multiplication mod 8.

(b) What is the multiplicative inverse of 5 mod 8?

52. Prove by contradiction that 15 does not have a multiplicative inverse mod 42.

53. Prove that if n is a positive integer, then

54. By constructing a table, show that has 4 solutions mod 6. (Note that quadratics "usually" have at most two roots!)

55. (a) Prove that the sum of the cubes of two integers does not leave a remainder of 4 when the sum is divided by 7.

(b) Prove that the Diophantine equation has no solutions.

1. Consider the set of integers

When the Well-Ordering Axiom is applied to S, it asserts the existence of a certain element of S. What is the element?

First

The integers which satisfy this inequality are 3, 4, 5, 6, and 7.

Well-Ordering says that a nonempty subset of the positive integers has a smallest element. The smallest element of S is 3.

2. (a) Let S be the set of real numbers x such that , with the usual ordering. Is S well-ordered?

(b) Let S be the set of integers x such that , with the usual ordering. Is S well-ordered?

(a) S is not well-ordered, because S has subsets which do not have smallest elements. For example, S itself does not have a smallest element (note that ).

(b) S is well-ordered. In fact, it is just , which is the set of positive integers translated 3 units to the right. Since the set of positive integers is well-ordered, S is as well.

3. Compute , , and .

4. Compute the exact value of .

Note that

So

Write out some terms of the sum:

Almost all the terms cancel in pairs, with a negative term cancelling with the positive term in the following expression. The remaining terms give the value of he sum:

5. Compute the exact value of .

Note that

So

Write out some terms of the product:

Most of the terms in the numerators cancel with terms in the denominators. The remaining terms give the value of the product:

6. Simplify to a single binomial coefficient.

Use the formula

Put and . Thus,

7. The Gamma function is defined by

Prove that if , then

Thus, the Gamma function satisfies the same kind of recursion relation as the factorial function.

Integrate by parts:

Then

The first term is 0 when and approaches 0 as . Therefore, the last equation becomes

8. Prove that if and , then

I'll expand the right side as factorials and combine the fractions over a common denominator:

9. Find the coefficient of in the expansion of .

occurs in the term . The full term is

The coefficient is .

10. Find and express it as a linear combination of 3914 and 2442.

Use the Extended Euclidean Algorithm:

Therefore,

11. Calvin Butterball has two egg timers that he bought after watching an ad on TV. One timer rings exactly 8 minutes after it is started; the other rings exactly 15 minutes after it is started. While each timer is running, no information about the time it is keeping is available. How can Calvin use the timers to time a 4-minute egg?

, and in fact,

Multiply by 4:

According to this equation, Calvin can do the following. Start both timers, restarting each timer when it rings. After the 15-minute timer has cycled 4 times, start cooking the egg. Stop cooking the egg when the 8-minute timer has cycled 8 times.

In the same way, Calvin can use the two timers to time *any*
integral number of minutes.

12. Find the greatest common divisor and least common multiple of and .

For the greatest common divisor, take the smallest power of each prime power the numbers have in common:

For the least common multiple, take the largest power of each prime power contained in either number:

13. The sum of two numbers is 2736. Their least common multiple is 77592. Find the numbers.

Suppose m and n are the numbers, so

Let p be a prime number that goes into both 2736 and 77592. Since 77592 is a multiple of m and of n, p must divide at least one of m and n.

If , then since , I have .

Similarly, if , then since , I have .

In other words, any prime factor of both 2736 and 77592 must be a
prime factor of * both* m and n.

It also goes the other way: If a prime p divides both m and n, then p clearly divides their least common multiple, as well as by a divisibility property.

Hence, the greatest common divisor of 2736 and 77592 is the same as the greatest common divisor of m and n.

By the Euclidean algorithm, . So I have

Note that, since 24 divides both m and n, the two fractions in the last equation are actually integers.

If I divide 24 out of both m and n, then 24 is divided out of their least common multiple. So

Since 24 was the greatest common divisor of m and n, the numbers and are relatively prime. Hence, their least common multiple is their product:

Then , so

You can solve this ugly quadratic using the Quadratic Formula; the roots are 1272 and 1464. Either root gives the pair of numbers , and they are the solution to the problem.

14. (a) If x is an integer, can be prime?

(b) If x is a positive integer, can be prime?

(c) If x is an integer, can be prime?

(a) Yes. If , then , which is prime.

(b) No. If , then and , so is a proper factorization (neither factor is equal to 1). Therefore, cannot be prime.

(c) Yes. If , then , which is prime.

(Don't make the mistake of thinking that since "doesn't
factor" as a * polynomial* over ,
that its * values* must always be composite.

15. Prove that if n is an integer and , then is not prime.

Note that

Since , both factors and are greater than 1. Hence, this is a proper factorization, and is not prime.

16. Prove that if leaves a remainder of 4 when it's divided by 5, then leaves a remainder of 3 when it's divided by 5.

Suppose that leaves a remainder of 4 when it's divided by 5. Then for . So

This shows that leaves a remainder of 3 when it's divided by 5.

Note: You can do this with less effort using *
modular arithmetic*.

17. Prove that the square of an integer does not leave a remainder of 2 when it's divided by 3.

Let . By the Division Algorithm, if n is divided by 3, there are 3 possibilities:

I'll consider the cases.

(a) .

In this case, leaves a remainder of 0 when it's divided by 3.

(b) .

In this case, leaves a remainder of 1 when it's divided by 3.

(b) .

In this case, leaves a remainder of 1 when it's divided by 3.

Therefore, the square of an integer never leaves a remainder of 2 when it's divided by 3.

Note: You can do this with less effort using *
modular arithmetic*. Just construct a tables of squares mod 3:

18. Give three integers a, b, and c such that a does not divide either b or c, but a divides .

For instance, and , but .

It * is* true that if a divides b and a divides
c, then a divides .

19. Let c, x, and y be integers, where . Prove that if and only if .

Suppose . Then for some k. Hence, . Therefore, .

Conversely, suppose . Then for some k. Since , the Zero Divisor Axiom for the integers allows me to cancel c from both sides: . This implies that , which completes the proof.

20. Calvin Butterball reasons that if , then and b must be relatively prime, because you've divided out of a all the factors that a and b had in common.

If he's right, prove it. If he's wrong, give a specific counterexample.

Take and . Then , so

But and aren't relatively prime. Hence, Calvin is mistaken.

21. Suppose . What are the possible values of ?

I have

The positive divisors of 4 are 1, 2, and 4, so the only possibilities are 1, 2, and 4.

If , then .

If , then .

If , then .

Thus, all three possibilities do occur.

22. Let n be a positive integer, and let x be an integer. Suppose that and . Prove that .

I have

Since n is a positive integer, I must have .

23. Prove that if and , then .

I have

Since , I must have . Thus, (and ) or (and ). Since , the first case is ruled out, so .

24. How many integers in the set are divisible by either 3 or 7, but not by both?

There are integers in which are divisible by 3.

There are integers in which are divisible by 7.

The integers divisible by * both* 3 and 7 are the
integers divisible by . There are of those. These are counted twice: Among the integers
divisible by 3, and among the integers divisible by 7.

Therefore, the number of integers in which are divisible by either 3 or 7, but not by both is

25. How many integers in the set are divisible by 3 but not 7?

There are integers in which are divisible by 3.

The integers divisible by * both* 3 and 7 are the
integers divisible by . There are of those.

Therefore, the number of integers in which are divisible by 3 but not by 7 is

26. Prove that if and n divides both and , then .

Since and , I have

27. Suppose that m and n are integers, and you know that

What are the possible values of ? Why?

The greatest common divisor of two numbers divides each of the numbers. Therefore, and . By divisibility properties, divides any linear combination of m and n. Hence,

Thus, is a positive integer that divides 35. The only positive integers that divide 35 are 1, 5, 7, and 35. Thus, must be one of these --- but are all of these possible?

I can show that all of these values *are* possible by finding,
for each case, specific values of a, b, m, and n for which , and for which is the desired number. I'll do
this by choosing m and n to give the desired number first, then
choosing a and b to get the linear combination to equal 35.

Take and , so . Then taking and , I also have .

Take and , so . Then taking and , I also have .

Take and , so . Then taking and , I also have .

Take and , so . Then taking and , I also have .

Thus, if , then is 1, 5, 7, or 35, and all four of these values are possible.

28. Prove that if n is a positive integer of the form , then n must have a prime factor of that form.

By the Division Algorithm, every integer may be divided by 4 leaving a remainder of 0, 1, 2, or 3. Therefore, every integer is equal to , , , or for some k.

Note also that an odd *prime* number can't have the form or
: Numbers of these forms are divisible by 2.

Consider . Factor n into a product of primes. is odd, since it's an even number ( ) plus an odd number (3). So n must be a product of odd primes.

These odd primes are either of the form or the form . Could all of them have the form ?

Notice that the product of two numbers of the form is a number of the form :

If all the prime factors of n have the form , then by induction n has the form as well. This contradicts the fact that .

Therefore, at least one prime factor of n has the form , which is what I wanted to prove.

29. Prove that if , then

For , I have

The result holds for .

Suppose that the result is true for n:

I must prove the result for :

I have

Therefore, the result is true for all by induction.

30. Prove that if denotes the Fibonacci number (where and ), then

31. Let denote the Fibonacci number (where and ).

Prove that if , then

For , I have

Thus, the result is true for .

Assume that the result is true for n:

I must prove the result for :

I have

To get the last equality, I used the Fibonacci formulas

Hence, the result is true for all by induction.

32. A sequence of integers is defined by

Prove that

First,

This establishes the result for and .

Assume the result is true for all :

I will prove the result for n. I have

This proves the result for n, so the result is true for all by induction.

33. Use induction to prove that for .

For , , while . The result is true for .

Let , and suppose the result is true for n:

Multiply both sides by :

For the second inequality, I used the fact that implies .

This proves the result for , so by induction the result is true for all .

34. Let . Prove that

For ,

Since , the result holds for .

Assume that the result holds for n:

Write this divisibility statement as an equation:

Then

The idea will be to substitute this into the -expression, and simplify to get stuff divisible by 9.

I have

The last expression is divisible by 9. Hence, the result is true for , and therefore true for all by induction.

35. Let be a polynomial with integer coefficients, and let be the derivative. Prove that

I'll use induction on the degree of f.

Suppose , where k is constant. Then

Therefore, the result is true for constant polynomials.

Let . Assume the result is true for polynomials of degree n, and let be a polynomial of degree :

Then

If I let , then is a polynomial of degree n. By the induction hypothesis,

Now by the Product Rule,

Putting all this together,

This completes the induction step, so the result is true for all polynomials, by induction.

36. Let x, y, and z be positive integers, and suppose the products , , and are all perfect cubes. Prove that x, y, and z must be perfect cubes.

An integer is a perfect cube if and only if each prime in its prime factorization occurs to a power divisible by 3. (Can you prove this?)

Let p be a prime factor of x, and suppose is the biggest power of p which divides x. I want to show that a is divisible by 3.

Let be the biggest power of p which divides y, and let be the biggest power of p which divides z. Then is the biggest power of p dividing , is the biggest power of p dividing , and is the biggest power of p dividing . Since , , and are all perfect cubes,

Hence,

So

But , so .

Since p was an arbitrary prime dividing x, every prime dividing x occurs to a power which is a multiple of 3. Therefore, x is a perfect cube. By symmetry, the same is true of y and z.

37. Suppose that p, q, and r are distinct prime numbers,

What are the possible values of y?

means , so and . Thus, or 1 and , 1, or 2. The possible values of y are

38. Suppose that the prime factorization of an integer n is

( , , and are distinct primes.)

Write n as a product of integers , where a is a perfect square
and b is * square-free* --- that is, b is not
divisible by the square of any positive integer except 1.

is clearly a perfect square.

can't be divisible by a perfect square other than . To prove this, suppose that , where d is a positive integer such that . Then , so , and d must be divisible by some prime number p by the Fundamental Theorem of Arithmetic. So , and hence

Thus, p must be a prime factor of the number , and the power of
p must be at least 2. But the prime factorization of
* is* , and the distinct primes and
both have power 1. This contradiction shows that
is square-free.

39. Find the prime factorization of 15400 by trial division.

Divide 15400 by 2 as many times as possible:

Divide 1925 by 5 as many times as possible:

Finally, it's clear that . So

40. Use Fermat factorization to factor 25877 into primes. (You should use Fermat factorization rather than some other method, and you should show the trial values.)

First, . So I will start my trials at 161.

Therefore,

You can check directly that 229 and 113 are prime, so this is the prime factorization.

41. Find the general solution to the Diophantine equation

Since , there are solutions. By inspection, , is a particular solution. The general solution is

42. Find the general solution to the Diophantine equation

A particular solution is and . The general solution is

43. Find the general solution to the Diophantine equation

Since , there are solutions.

Note that . So write the equation in the form

Let

Then

, so there are solutions. By inspection, , is a particular solution. The general solution is

Hence,

, so there are solutions. To find a particular solution, write as a linear combination of 2 and -3:

Multiply by :

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

(Note: You might have expected the " " and " " terms to have opposite signs. The reason they don't is that the coefficients of the x and y terms in the original equation are "+" and "-", instead of both "+" as is often the case.)

All together, the solution to the original equation is

44. Bonzo buys some books that cost $7 each and some books that cost $15 each. The books cost a total of $349. What is the largest total number of books Bonzo could have bought?

Let x be the number of $7 books and y be the number of $15 books. Then

and is a particular solution. The general solution is

Since the numbers of books can't be negative, I have and .

The integer values of t satisfying both inequalities are .

The total number of books is

The largest total number of books is 43, consisting of 37 7-dollar books 6 15-dollar books.

45. I. M. Snarky buys 43 apples and oranges. The apples cost 10 cents more than the oranges, and he spends a total of $30.68. Find the number of each fruit that he bought and their prices.

I will do everything in cents.

Let x be the number of apples, and let y be the number of oranges. Then

Suppose the oranges cost c cents each. Then the apples cost cents each. The total cost of the fruit is

By trial and error or the Extended Euclidean Algorithm, I have

Thus, a particular solution is and , and the general solution is

Now , so

Since , I have .

Also, , so

Thus, , so .

All together, I find that t is an integer and . I check the values:

He bought 23 apples and 20 oranges. The apples cost 76 cents each, and the oranges cost 66 cents each.

46. Solve the following Diophantine equation by factoring:

Rewrite the equation:

7 may be factored into the product of two integers in 4 ways. I'll take cases.

Case 1: and .

Subtracting the equations gives , which has no integer solutions.

Case 2: and .

Subtracting the equations gives , which has no integer solutions.

Case 3: and .

Subtracting the equations gives , which has no integer solutions.

Case 4: and .

Subtracting the equations gives , which has no integer solutions.

Therefore, the original Diophantine equation has no solutions.

47. Is prime?

Note that

So

This means that the units digit of is 5. Since is obivously greater than 5, it's not prime because it's divisible by 5.

48. Find .

Use the Extended Euclidean algorithm:

Hence, .

49. Suppose that . Prove that if and , then .

Since , I have

Likewise, since and , I have

Then

Thus, , so .

50. Prove that if , then is not divisible by 5.

If , then . Contruct a table:

In every case, . Hence, if , then is not divisible by 5.

51. (a) Construct a table for multiplication mod 8.

(b) What is the multiplicative inverse of 5 mod 8?

(b)

(b) Since , the multiplicative inverse of 5 mod 8 is 5.

52. Prove by contradiction that 15 does not have a multiplicative inverse mod 42.

Suppose . I notice that , and . Multiply the equation by 14 and simplify:

This contradiction proves that 15 does not have a multiplicative inverse mod 42.

53. Prove that if n is a positive integer, then

* Method 1.* Write and expand
the right side using the Binomial Formula:

All of the terms except the last two are divisible by . Therefore,

* Method 2.* I'll use induction. For ,

So the two sides are equal (so they're equal mod 36).

Assume the result is true for n:

I'll prove it for :

This proves the result for , so it's true for all , by induction.

54. By constructing a table, show that has 4 solutions mod 6. (Note that quadratics "usually" have at most two roots!)

The solutions mod 6 are , , , and .

55. (a) Prove that the sum of the cubes of two integers does not leave a remainder of 4 when the sum is divided by 7.

(b) Prove that the Diophantine equation has no solutions.

(a) Make a table of cubes mod 7:

The possible values of are 0, 1, and 6. There is no way to make 4 as the sum of two of these numbers. Hence, if , then . This means that the sum of the cubes of two integers does not leave a remainder of 4 when the sum is divided by 7.

(b) If for , then . But part (a) shows that has no solutions. Hence, the Diophantine equation has no solutions.

Note: This method can *sometimes* be used to show that a
Diophantine equation has no solutions. One problem here is to choose
a good modulus. For instance, it would not help to reduce mod 2, since does have
solutions.

*When a dog runs at you, whistle for him.* - *Henry David
Thoreau*

Copyright 2020 by Bruce Ikenaga