01204211/homework6 number theory 1

This is part of 01204211-58

Due: 21 Oct, 2015

H.1 (LPV-6.1.3) Prove that if $a|b$ and $a|c$, then $a|b+c$ and $a|b-c$.

H.2 (LPV-6.10.3) Prove that if $c\neq 0$ and $ac|bc$, then $a|b$.

H.3 Prove that for integers $a$ and $b$ and positive integer $q$ the following statements are true.

(a) $(a+b)\;{\bmod {\;}}q=((a\;{\bmod {\;}}q)+(b\;{\bmod {\;}}q))\;{\bmod {\;}}q$

(b) $(ab)\;{\bmod {\;}}q=((a\;{\bmod {\;}}q)\times (b\;{\bmod {\;}}q))\;{\bmod {\;}}q$

Notes: this fact may be useful: If $r=a\;{\bmod {\;}}q$, then there exists an integer $k$ such that $a=kq+r$.

H.4 (LPV-6.1.6) (a) Prove that for every integer $a$, $a-1|a^{2}-1$.

(b) More generally, prove that for every integer $a$ and positive integer $n$, $a-1|a^{n}-1$.

H.5 (LPV-6.3.3) Suppose that $a$ and $b$ are integers and $a|b$. Suppose that $p$ is a prime and $p|b$, but $p\not |a$. Prove that $p|(b/a)$.

H.6 Let $p$ be a prime. Consider integers $a$ and $b$, such that $1\leq a,b\leq p-1$. Prove that if $a\ {\bmod {p}}=b\ {\bmod {p}}$ then $a=b$.

H.7 (LPV-6.10.7) Prove that if $a>3$, then $a$, $a+2$, and $a+4$ cannot be all primes. (Can they all be powers of primes?)

H.8 (LPV-6.10.14) Find pairs of integers for which the Euclidean Algorithm runs for (a) 2 steps, and (b) 6 steps.

Notes: Recall that the Euclidean algorithm GCD(a,b) is defined as:

FUNCTION GCD(a,b)
1.  if b|a then return b endif
2.  return GCD(b, a mod b)

In this problem let's count the number of steps the algorithm runs by the number of times function GCD is called. For example, GCD(8,2) runs 1 one step, but GCD(18,10) runs for 3 steps. In this problem, you only have to give examples of pairs for cases (a) and (b).

H.9 (LPV-6.10.16) Prove that for every positive integer $m$, there is a Fibonacci number, beside $F_{0}=0$, divisible by $m$. For example, when $m=4$, we have $F_{6}=8$ which is divisible by $m$.