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:

(1)

\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$.)