Number Systems: Problem Sheet 4

Here are some hints for Problem Sheet 4 given to people in office hours.

Correction: There is a small typo on page 15 of the lecture notes: in the second line of Example 3.12, \frac{1}{6}k(k+1)(2k+1) should read \frac{1}{6}n(n+1)(2n+1). This has been corrected on the version now on Moodle.

Question 4: first try some small examples to get a feeling for what’s going on. (You should always do this for any problem, even if you think you can easily solve it in the general case.) For instance, if n=2 then

(21n+4)/(14n+3) = 46 / 31,

and if n=3 then

(21n+4)/(14n+3) = 67 / 45.

In both cases the numerator and denominator have no common factors, so the fraction is in lowest terms. This can be seen directly, but if n is larger we would prefer to use Euclid’s Algorithm, and this is essential to solve the general problem. For example, if n=10 then the fraction is 214 / 143 and since 214 = 143 + 71, and 143 = 2 \times 71 + 1, we have

\mathrm{gcd}(214,143) = \mathrm{gcd}(143,71) = \mathrm{gcd}(71,1) = 1.

Hence 214 and 143 have no common divisors. (The prime factorizations are 214 = 2 \times 107 and 143 = 11 \times 13.)

You should find that a similar pattern of divisions occurs if you apply Euclid’s Algorithm in the cases n=2 or n=3. For example, the first quotient is always 1, since 21n + 4 = 1 \times (14n+3) + 7n+1. This might give you the confidence to try the general case.

Question 6: There is a short solution using the uniqueness of prime factorization (see Theorem 4.12). This question should seem much easier after Monday’s lecture.

Question 5: Hint: since n is not prime, n/p has a prime divisor. If p > \sqrt{n}, then n/p < \sqrt{n} so n/p must have a prime factor that is less than \sqrt{n}. Try to get a contradiction from this. You could also seee the lecturer on Wednesday afternoon, or try reading the answers to this question on Math.StackExchange.

You are welcome to add a comment below or email me with any questions.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: