Test 1

- ( 16 points) Complete the following sentences
- Dirichlet's Theorem states…
- For a given integer
*n*, $\nu(n)$ counts…

- (15 points) Answer the following questions either “true” or “false.” If true, give a
**brief justification**; if false, give a**specific counterexample**. In all examples,*a,b,c*and*m*are all integers.*a*does not have a multiplicative inverse modulo*m*if and only if $a \mid m$.- If $ca \equiv cb \mod{m}$ then $a \equiv b \mod{m}$.
- If $(a,m) = (b,m) = 1$, then
*ab*is relatively prime to*m*.

- (12 points) Is $217 = 7\cdot 31$ a psuedoprime?
- (12 points) Express gcd(201,177) as an integral linear combination of 201 and 177.
- (12 points) For each of the following linear congruence equations, determine how many incongruent solutions exist. If solutions do exist, provide
**one**solution.- $177x \equiv 7 \mod{201}$
- $177x \equiv 12 \mod{201}$

- (12 points) Solve the following simultaneous system of congruences:

\begin{align} \begin{split} x&\equiv 3 \mod{7}\\ x&\equiv 5 \mod{11}. \end{split} \end{align}

- (15 points) How many integers between 1 and 1980
- are divisors of 1980?
- are
**NOT**relatively prime to 1980?

- (10 points) Suppose that
*p*and*q*are a twin prime pair with $3 < p,q$. Prove that $pq+1$ is a perfect square that is divisible by 9. (Hint: division algorithm with $d=3$.)

page revision: 3, last edited: 01 Oct 2008 20:20