Numbers and Sets | Part IA, 2003

Let m,nm, n be integers. Explain what is their greatest common divisor (m,n)(m, n). Show from your definition that, for any integer k,(m,n)=(m+kn,n)k, \quad(m, n)=(m+k n, n).

State Bezout's theorem, and use it to show that if pp is prime and pp divides mnm n, then pp divides at least one of mm and nn.

The Fibonacci sequence 0,1,1,2,3,5,8,0,1,1,2,3,5,8, \ldots is defined by x0=0,x1=1x_{0}=0, x_{1}=1 and xn+1=xn+xn1x_{n+1}=x_{n}+x_{n-1} for n1n \geqslant 1. Prove:

(i) (xn+1,xn)=1\left(x_{n+1}, x_{n}\right)=1 and (xn+2,xn)=1\left(x_{n+2}, x_{n}\right)=1 for every n0n \geqslant 0;

(ii) xn+3xn(mod2)x_{n+3} \equiv x_{n}(\bmod 2) and xn+8xn(mod3)x_{n+8} \equiv x_{n}(\bmod 3) for every n0n \geqslant 0;

(iii) if n0(mod5)n \equiv 0(\bmod 5) then xn0(mod5)x_{n} \equiv 0(\bmod 5).

Typos? Please submit corrections to this page on GitHub.