BAMO math circle, March 25,2001

V. Serganova Diophantine equations.

1. A grasshopper can jump $p$ or $q$ inches right or left on the line. Find all points on the line the grasshopper can reach starting from the origin.

2. Prove that the minimal positive integer $d$ of the form $d=mp+nq$ coincides with the Greatest Common Divisor of $p$ and $q$, and that $GCD(p,q)$ can be found by the following Euclidean algorithm:

Divide $p$ by $q>0$ with the remainder $r$: $p=lq+r$ where $q>r\geq 0$. If $r>0$, proceed with $q,r$ instead of $p,q$. If $r=0$, stop. The last non-zero remainder $d$ equals $GCD(p,q)$.

3. Diophantine equation $ax+by=c$ has a solution $(x,y)$ if and only if $c$ is divisible by $d=GCD(a,b)$. If $(x_0,y_0)$ is a solution, then any other solution can be written in form $x=x_0+sb/d, y=y_0-sa/d$ for some integer $s$.

4. The equation $x^2-y^2=10$ does not have integer solutions.

5. Prove that the equation $x^2+y^2=z^2$ has infinitely many non-proportional integer solutions.

6. Find all integer solutions of the equation $x^2-y^2=2001$.

7. Obtain a formula for all rational solutions of $x^2+y^2=1$. For this consider an inversion on the plane with center at the point $\left(0,1\right)$ and radius $2$. Show that the inversion maps the $x$-axis onto the unit circle with center at the origin without the point $(0,1)$. Prove that a rational point on $x$-axis moves to a point with rational coordinates on the circle.

8. Prove that sums, differences, products and ratios of numbers of the form $a+b\sqrt{2}$, where $a,b$ are rational, also have this form. Is it true if $a,b$ ought to be integer?

9. Theorem: the equation $x^2-2y^2=1$ has infinitely many integer solutions. Hint: Prove that if $(a,b)$ and $(c,d)$ are two solutions then $(ac+2bd, ad+bc)$ is a solution too.

10. Put $N(a+b\sqrt{2})=(a+b\sqrt{2})(a-b\sqrt{2})=a^2-2b^2$. Show that $N(AB)=N(A)N(B)$.

11. Find all numbers $A=a+b\sqrt{2}$ with integer $a,b$ such that $N(A)=1$.

Homework

1. A Heffelump is a chess piece which moves like Knight but with $p$ steps in one direction and $q$ steps in the perpendicular direction. Determine for which $p$ and $q$ the Heffelump, starting from one cell on the infinite chess board, can reach any other cell.

2. Solve the following Diophantine equations:

(a)$161x+7y=1$;

(b)$4x+13y=1$;

(c)$3x+5y=41$;

(d)$xy=x+y$;

(e) $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1$.

3. Show that the equations below do not have integer solutions:

(a) $x^4+y^4=10$;

(b) $x^2+y^2=7z^2$;

(c) $x^2-3y^2=2$;

(d) $x^2-3y^2=7$;

(e) $x^2-2y^2=3$

4. Write recurrent formulae for all integer solutions of the following equations:

(a) $x^2-2y^2=2$;

(b) $x^2-3y^2=1$;

(c) $x^2-3y^2=6$.

5. Show that if $p$ is prime then the equation $x^2-py^2=1$ has infinitely many solutions.

(a) Show that one can find an integer $b$ such that $x^2-py^2=b$ has infinitely many solutions.

(b) Let $\left(x_1,y_1\right)$ and $\left(x_2,y_2\right)$ be two solutions of the equation from (a), $x_1$ and $x_2$ have the same remainder when divided by $b$ and $y_1$ and $y_2$ have the same remainder when divided by $b$. Let $Z[\sqrt{p}]$ be the set of all numbers $a+b[\sqrt{p}]$ with integer $a$ and $b$. Prove that $\frac{x_1+y_1\sqrt{p}}{x_2+y_2\sqrt{p}}$ belongs to $Z[\sqrt{p}]$ and has norm $1$.

(c) Using (b) obtain infinitely many solutions for $x^2-py^2=1$.