Math 480 (Spring 2007): Homework 1

Due: Monday, April 2

There are 7 problems. Each problem is worth 5 points, and parts of multi-part problems are worth equal amounts.
Office Hours. My official office hours are on Thursdays 4-6pm in Padelford C423.

1. (This problem must be done without help from anyone else.) 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$ .

2. (This problem must be done by hand without help from anyone else.) 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.$$

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

4. 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$ .

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

6. 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}$ .

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