# Number Theory study problems

### Problem 1

Trace the execution of textbook's code for the Euclidean algorithm on the inputs
• a = 6409
• b = 42823

Give a table showing the values of the main variables x,y, r for each pass through the loop. Explicitly indicate the output value.

Check your solution against the annotated solution

### Problem 2

Prove the following claim directly from the definition of divides'' (i.e. don't use facts about divides proved in class or the book). A direct proof should work.

Claim: For any integers p, q, and r, where p is non-zero, if $$p \mid 3q$$ and $$3q \mid r$$, then $$p \mid 3q + r$$.

Write out your solution, actually write it out on paper, before consulting the annotated solution.

### Problem 3

Do this problem after you've checked your answer to the previous problem.

In the book, you will find several equivalent ways to define congruence mod k. For this problem, use the following definition: for any integers x and y and any positive integer m, $$x \equiv y \pmod{m}$$ if there is an integer k such that x = y + km. Using this definition prove the following claim

For all integers a, b, c, p, q where p and q are positive, if $$a \equiv b \pmod{p}$$ and $$c \equiv b \pmod{q}$$ and $$q | p$$, then $$a -2c \equiv (-b) \pmod{q}$$.

Write out your solution and then consult the annotated solution.

### Problem 4

Prove or disprove:

Claim: For all positive integers a, b c, if $$a \mid bc$$, then $$a \mid b$$ or $$a \mid c$$.

Stuck? See the hints.

Write out your solution and then consult the annotated solution.

### Problem 5

Recall that gcd(p,q) is the largest integer that divides both p and q. Use proof by contrapositive to prove the following claim:

Claim: For all integers a and b, if $$3a-5b = 27$$, then $$\gcd(a,b) \not = 13$$.

You must work directly from the definitions, not using facts we might have proved about (say) divisibility.

Write out your solution and then consult the annotated solution.

### Problem 6

Siebel Bakery offered free muffins for people studying CS173. The baker claimed that they gave out a total of $$n^2 + 9n - 2$$ muffins. 11 men and n women got muffins and each person was given the same number of muffins.

(a) Is there a solution to this problem for which $$n\le 11$$?

(b) Is there a solution when $$n > 11$$?

For each part, provide either an example or a proof that no example can exist. You may use simple facts about divisibility, e.g. you can use the fact that if a|b and a|c then a|(b+c). You don't need to take everything back to the basic definition of divisibility.