Remarks on 2201 exam

I received a lengthy email with a number of general questions about the 2201 exam. I suspect the reply will be of relevance to many people, so I’m posting a rather detailed reply. Try to give it a good reading.

1) there will be 6 questions in the exam paper; how do you divide these according to our syllabus; is it similar to the past papers or you can tell me with regard to the course summary i.e 2 from part 1 etc.


If you take the chapters from the course notes the distribution is: 1 problem from each of the first three chapters and three problems from the last two chapters.

2) will your question style be similar to the homework sheets or the available past papers.


Combination of both of course. Among the past exams, the last three seem to be more relevant than the earlier ones. However, you should be aware that *similarity of style* is a highly subjective notion. More precisely, if you understand the material well, many things appear similar. With a superficial understanding, small differences can be terrifying, even small typos.

3) what is the ratio of theorem and proof questions to calculation questions.


I wouldn’t quite divide the material up in this way. But the portion of the exam where you are expected to prove an assertion coming from a standard theorem is worth around 10~30 points , depending on which problems you select. This does not mean you can avoid *understanding* many proofs. More on this below.

4) could you please list the theorems you expect us to reproduce. i know i need to cover all, but some are required to do calculation while others are to be reproduced. i understand them but reproducing somehow is difficult for me. if i have a list, i can revise them in a way, keeping in mind that i need to reproduce them; such as if a is congruent to a’ and b is congruent to b’ (mod m) then a+a’= b+b’ and aa’=bb’


Many students have expressed concerns about `reproducing’ the proof of a theorem. I would rather say that you need to come to a confident understanding of the proofs. This means you should feel comfortable with the main points rather than being able to read (or even memorize) line by line. In practice, this also means connecting the different parts of a section, chapter, or the whole course. With any given proof, ask yourself what the key idea is. If you’ve done this through sufficiently many readings, then memorization becomes unnecessary. I will try to illustrate this a bit with another of your questions below. But rest assured that if you’ve understood the main point of a theorem, a small defect in memory will not cause a problem in the exam.

5) i am following the web lecture notes since my class lecture notes are sketchy; is there anything i need to eliminate or add? however i refer to them.


You should go through the whole set. Supplement with at least the starred material from the course website.

6) c is prime to m; does this imply that c and m are coprime?


Yes. The following terminology often refers to the same condition:

-c is prime to m;
-c and m are coprime;
-c and m are relatively prime.

The condition is that the highest common factor (or greatest common divisor) of c and m is 1. Equivalently, if you look at the prime factorization of the two numbers, the set of primes that occur for the two numbers should be disjoint.

7) how important is RSA cryptography regard to exams


It’s not so directly important. But the notions that occur there, namely, taking powers modulo a number, inverting modulo a number, using the Chinese remainder theorem, and so forth, you should understand well.

8) i had this in my notes, please tell me if i have it correct and do we use this in our exam; prime number theorem

X/logX ~ primes less than X


This is correct. However, this is not material you will be tested on. I discussed this before I was aware of the importance of distinguishing the tested material from the add-ons.

9) in the web notes for the ‘unique factorization theorem’ it says if a>/2 (if a is greater than equal to 2) is an integer then there are primes > 0 such that a can be written as prime factorization. but how can we write 2, 3 as prime factorization since 1 is not a prime


Both 2 and 3 are themselves primes. So the prime factorization equation for them would look like

2=2, 3=3

It only becomes non-trivial with non-primes (composite numbers). So, for example


By the way, it is the *uniqueness* of the factorization that is the more interesting fact. This shows, for example, that a power of 2 can never be of the form

(1 followed by many zeros).

Why not?

10) coprime is when both numbers are prime and so their hcf is equal to 1


The sentence as written is incorrect. If you say `both numbers are prime’ then you are requiring indeed both numbers to be prime. As discussed above, the correct definition is what follows your `so’. That is, you should have written: Two numbers are coprime when their hcf is 1.


-10 and 21 are coprime although neither are prime.

– 2 and 3 are *both* primes.

Now if you think about it a second, you will see that if you have two numbers that are both primes and distinct, then they *are* coprime, as in 2 and 3. But you can’t say this `the other way around.’

11) in the notes it was written that natural numbers = {0,1,2….} but i believe natural = { 1,2,…..} and whole numbers = {0,1,2…}; please clear


This is a rather simple matter of convention that shouldn’t bother you too much. But it is true that mathematicians usually prefer to include 0 in the natural numbers.

12) in mentioning unique factorization theorem does the order of primes matter?


It depends on the context you have in mind. If you are stating the unique factorization theorem precisely, for example, it is important to point out that the uniqueness is only true *up to reordering*. That is, if

n=p_1p_2\cdots p_s

and also

n=q_1q_2 \cdots q_t,

where the p_i and q_j are all prime, the theorem is *not* saying p_1=q_1, p_2=q_2 and so on.
It is saying:

s=t; and
-There is a permutation \sigma of {1,2,\ldots, s} such that p_i=q_{\sigma(i)} for each i. That is, the primes that occur are the same *up to reordering*.

Having said this, suppose the question you encounter is to *find* the prime factorization of a number. Then it’s not important what order you put it in, although some people might like to fix a convention. That is, you can write

1000=2^3 5^3


1000=5^3 2^3

But it is probably a good idea to group the same primes together rather than write, say

1000=2\cdot 5\cdot 2 \cdot 5\cdot 2\cdot 5

13) there are two euclid’s theorems; when you are to ask for one how do we know which to write.


If such a question occurs, the context will make it clear which one is being asked for.

14) the diophantine equation; ax+by=n; is it the one that takes the multiple of the hfc of a and b into consideration.


Yes. Try to state this more precisely for yourself. That is, what exactly is the condition for the existence of a solution in integers? (This is carefully discussed in the notes.)

15) there are in the web notes some corollary which are not part of ur lec notes nor the summary; what to do; such as 1.3.13, 1.3.14


This is the kind of situation you should think about more carefully. It is important to understand how the different items connect up. In fact, at the end of the course, you could say that understanding the *flow* of the subject is the *most* important thing. Specific to your question, note that 1.3.14 uses 1.3.13. And then 1.3.14 is used in 1.3.15. The use of Fermat’s little theorem is of course ubiquitous.

In short, the assertion that they do not occur in the notes or the summary is rather strongly false. I say this in a somewhat strong way because coming to an understanding of such an issue could be very important for many of your other courses as well. The point is, once again: The material comes together in its entirety. To think that some result *does not occur* because it’s not explicitly listed is not a satisfactory level of understanding. Of course I’m sure you can remedy that.

16) do you require bezout’s lemma proof or is it just its application


In this case, perhaps I will say that knowing how to use the theorem is more important than remembering the proof.

17) in solving inverse congruency questions, for example inverse 5 ( mod 12 ):

12 = 2 x 5 + 2
5 = 2 x 2 + 1

once we get 1 we do the following

1 = 5 – 2 x 2
= 5 – 2 x ( 12 – 2 x 5 )
= 5 x 5 – 2 x 12

hence 5 is congruent to inverse of 5

however, if we get a negative i.e

1 = (-34)3 + 103

this implies inverse 3 is -34 but how do we calculate this further to get a positive answer; in tis case 69, as in the web notes


Here, I presume we are working modulo 103. The point is that inside the set

{ 0,1, \ldots, 102}

that we use to represent the congruence classes, the number you add to 34 to get 0 is 69, because

34+69=103 \equiv 0 ( mod 103)

In the additive group of \mathbb{Z}/103 we can concisely write this


Yet another way to say this is to note that


so that

1=69\cdot 3-2\cdot 103,

which implies

1 \equiv 69 \cdot 3  \ mod  \ 103

This displays more explicitly 69 as the inverse of 3 modulo 103.

18) in the summary you have mentioned that how is bezout’s lemma used in the proof of unique factor theorem; i cant find how we use it cuz i believe i haven’t used it in my proof; please explain how we use it; i have attached my proof os the theorem


Here, the issue is again similar to question (15). The whole reason for asking this was to get students to examine at least some key ingredients of the proof, not to get them to memorize what’s written in the notes.
In the proof of theorem 1.2.8, the main point in the uniqueness part is corollary 1.2.7, which, in turn, just generalizes theorem 1.2.6. This theorem says

if a prime divides the product of two numbers, then it has to divide one or the other.

It is this key property of primes that is used many times in elementary arithmetic. The proof of this theorem, of course, relies crucially on Bezout’s lemma.


Anyways, thank you for all these questions! I’m sure it will be useful to other students who have wondered about similar things. Please feel free to ask again after thinking about matters a bit. My own strong commitment is to helping all who wish to come to a comfortable understanding of the material rather than trembling in fear over what proofs need to be memorized!



One Comment

  1. SL
    Posted March 3, 2008 at 2:45 pm | Permalink | Reply

    Blimey someone was doing his revision!! I’d better start too!!!:p

    p.s. really no past paper answer available at all?

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: