# Number Theory study problems

### Problem 1

Trace the execution of textbook's code for the Euclidean algorithm on the inputs
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.

hints

solution to (a)

solution to (b)