## 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.