Exercises

1..

1. Compute the greatest common divisor $\gcd(455,1235)$ by hand.

2. Use the Sieve of Eratosthenes to make a list of all primes up to $100$ .

3. Prove that there are infinitely many primes of the form $6x-1$ .

4. Use Theorem 1.2.11 to deduce that $$\lim_{x\to\infty} \frac{\pi(x)}{x} = 0$$ .

5. Let $\psi(x)$ be the number of primes of the form $4k-1$ that are $\leq x$ . Use a computer to make a conjectural guess about $\lim_{x\to\infty} \psi(x) / \pi(x)$ .

6. So far $44$ Mersenne primes $2^p-1$ have been discovered. Give a guess, backed up by an argument, about when the next Mersenne prime might be discovered (you will have to do some online research).

7. 1. Let $y=10000$ . Compute $\pi(y) = \char93 \{$   primes $p \leq y\}.$
   2. The prime number theorem implies $\pi(x)$ is asymptotic to $\frac{x}{\log(x)}$ . How close is $\pi(y)$ to $y/\log(y)$ , where $y$ is as in (a)?

8. Let $a,b,c,d$ , and $m$ be integers. Prove that
   1. if $a\mid b$ and $b\mid c$ then $a\mid c$ ,
   2. if $a\mid b$ and $c\mid d$ then $ac\mid bd$ ,
   3. if $m\neq 0$ , then $a\mid b$ if and only if $ma\mid mb$ , and
   4. if $d\mid a$ and $a\neq 0$ , then $\vert d\vert\leq \vert a\vert$ .

9. In each of the following, apply the division algorithm to find $q$ and $r$ such that $a = bq + r$ and $0\leq r< \vert b\vert$ :
   $$a=300, b=17,\quad a=729,b=31,\quad a=300,b=-17,\quad a=389,b=4.$$

10. 1. (Do this part by hand.) Compute the greatest common divisor of $323$ and $437$ using the algorithm described in class that involves quotients and remainders (i.e., do not just factor $a$ and $b$ ).
    2. Compute by any means the greatest common divisor
       $$\gcd(314159265358979323846264338, 271828182845904523536028747).$$

11. 1. Suppose $a$ , $b$ and $n$ are positive integers. Prove that if $a^n\mid b^n$ , then $a\mid b$ .
    2. Suppose $p$ is a prime and $a$ and $k$ are positive integers. Prove that if $p \mid a^k$ , then $p^k \mid a^k$ .

12. 1. Prove that if a positive integer $n$ is a perfect square, then $n$ cannot be written in the form $4k+3$ for $k$ an integer. (Hint: Compute the remainder upon division by $4$ of each of $(4m)^2$ , $(4m+1)^2$ , $(4m+2)^2$ , and $(4m+3)^2$ .)
    2. Prove that no integer in the sequence
       $$11, 111, 1111, 11111, 111111, \ldots$$
       is a perfect square. (Hint: $111\cdots111 = 111\cdots 108 + 3 = 4k+3$ .)

13. Prove that a positive integer $n$ is prime if and only if $n$ is not divisible by any prime $p$ with $1 < p \leq \sqrt{n}$ .