Solutions to Math 2020 homework

Solutions to Math 2020 homework 2

To fit on the paper better, I’ll start with 4 first:
4. find a proof by contradiction for the statement “ is irrational”, using the following steps:
o. Aiming for a contradiction, assume x is rational . (The opposite (or negation) of what we want to prove.)
i. Use the definition: What does it mean for x to be rational?
ii. Use the definition: What does it mean for ?
iii. Put i and ii together, and use some properties of logatithms, e.g., , so that from the equality
you get another equality, involving only integers, and using notation introduced in steps i and ii .
iv. Use a previous result , in this case, apply unique prime factorisation.
v. Derive a contradiction. This means that step o was wrong, so x is irrational. QED

Proof that is irrational:
Suppose that x was rational. Then for some integers a, b, we have x = a/b.
By definition, if

, then 10^x = 5.
Note that since 5 is greater than 1, this means x must be positive, so a and b can also be taken to be positive.
Substituting x = a/b into 10^x = 5 gives

, now take b powers of both sides, to get

,
where a and b are positive integers .
But

is even, and 5^b is odd, so we have an odd number equal to an even number, which is
impossible.
So the original assumption that x is irrational must have been wrong.
So x must be irrational. QED

As discussed in the class before the homework is due, it’s useful to do question 3 before question 1:
3. For any positive integer m, the polynomial (x − 1) divides x ^m − 1. What is the quotient?

First, note that (x − 1) does divide the polynomial f (x) = x^m − 1.
This follows from the result that says that

(x − a) is a factor of

.

So, this means we can make the division, with no remainder. What we get is:

or in other words,

There are several ways to show this; we can use long division of polynomials (which you should be able to do), or proof
by induction (which we’ve not discussed), or else you can just prove that
by a direct computation:

(since all the terms apart from these cancel)

As discussed in class, there is another useful factorisation to know, closely related to the above:

If m is odd, then

or in other words,

This can be proved by a similar direct caclulation as above, or else by substituting x = −t in the previous formula,
and then changing t to x .

1. Find the prime factorisations of

Several factors can be found by applying the formulas above :

apply formula with m = 3
apply formula with m =
multiply out expressions in previous line
factor by hand
collect terms

You now need to check that 331 is prime, e.g., by checking that it is not divisible by any prime up to
i.e., check to see it is not divisible by 2, 3, 5, 7, 11, 13, 17.

apply formula with m = 2
apply formula with m = 2 and m = 3

apply formulas three times, with m = 3
multiply out expressions in previous line
factor by hand
collect terms

Note, here we had to factor 4033 by hand, by trial and error — just try all the primes up to it’s square root . Then
we also have to check that all the factors we have now are prime, by a similar check.

Other examples work similarly; the final solutions will be:

You’ll have to check that 4561 is prime by checking whether it’s divisible by primes up to .

2. Find four prime divisors of 34¹¹⁰ − 1.

Using the same formulas as above, you can show this is divisble by 34 − 1 = 33 = 3 × 11 and 34 + 1 = 35 = 5 × 7 —
see example in lecture notes. So four factors are 3, 5, 7, 11.

It’s actually quite hard to get much further than this. You can factor x¹¹⁰ − 1 further; you’ll get the following
factors:

These correspond to taking m = 2, 5, 11 in the formulas, so this should not be too hard for you to find these factors.

Now substitute x = 34 in each of these, to get: 34¹¹⁰ − 1 = 33 × 35 × 1298155 × 1376831 ×
2005395532515211 × 2126934655697951 × 17627540212819617844689862114783831422833360078884264641455551 ×
18695875160328810169167158861547301154574255477637705071514051
Although these are much smaller than
34¹¹⁰ − 1 = 29018895238801783362919436669661248997371936893563382617698314869110886802804922874846
99995832981992449680614659986691478886127783582332100503137691233968267549292363775,
these numbers are still too big for most computers to factor in a reasonable length of time.
But the question only asked for 4 factors, so at least you don ’t need to try and factor these huge numbers for
homework.