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, should read . 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 then

and if then

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 is larger we would prefer to use Euclid’s Algorithm, and this is essential to solve the general problem. For example, if then the fraction is and since , and , we have

Hence and have no common divisors. (The prime factorizations are and .)

You should find that a similar pattern of divisions occurs if you apply Euclid’s Algorithm in the cases or . For example, the first quotient is always , since . 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 is not prime, has a prime divisor. If , then so must have a prime factor that is less than . 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.

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Friday, October 26th, 2012 at 6:48 pm and is filed under Number Systems. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.