Agreement: All numbers on this page are integer numbers.

Problem 1. Show that for any $a$ and $b\ne0$ there are unique $q$ and $r$ such that $a=qb+r$ with $0\leqslant r < |b|$. Send a solution

∆ Definition 1. The numbers $q$ and $r$ described above are called quotient and reminder correspondingly.

Problem 2. Compute quotient and reminder dividing 1) $-17$ by $4$; 2) $23$ by $-7$; 3) $-1$ by $-5$. Send a solution

Problem 3. What quotients are possible when dividing $59$? Send a solution

Problem 4. Compute quotient and remainder dividing 1) $n^2$ by $n+1$; 2) $n^2+n+1$ by $n-1$; 3) $2^{100}-1$ by $2^7-1$; 4*) $2^{m}-1$ by $2^{n}-1$. Send a solution

Problem 5. * 1) Show that $a^{2k+1}+1$ is divisible by $a+1$ with zero remainder. 2) Find the remainder dividing $a^{2k}+1$ by $a+1$. Send a solution

∆ Definition 2. The greatest common divisor of $a$ and $b$ is the largest number that divides both of them without leaving a remainder. Notation: $GCD(a,b)$.

Problem 6. Show that for any $a$ and $b$, where $a\ne 0$ or $b\ne 0$, there is a unique $GCD(a,b)$. Send a solution

Problem 7. Show that for any $a$, $b$ and $c$ ($a\ne0$ or $b\ne0$) 1) $GCD(a,b)\geqslant1$; 2) $GCD(a,b)=|a|\Longleftrightarrow b⋮ a$; 3) $GCD(a,ca+b)=GCD(a,b)$. Send a solution

Problem 8. (Euclidean algorithm) The Euclidean algorithm proceeds in a series of steps. Let $(a,b)$ be a pair of positive numbers such that $a\geqslant b$. The first step is to consider a pair $(b,r)$, where $r$ is the remainder from division $a$ by $b$. In the next step, insead of the pair $(b,r)$ we consider a pair $(r,r_1)$ using the same rule. We stop once we get a pair of the type $(d,0)$. Show that 1) the process has an end; 2) $d=GCD(a,b)$. Send a solution

Problem 9. Using the Euclidean algorithm, compute 1) $GCD(91,147)$; 2) $GCD(-144,-233)$. Send a solution

Problem 10. Consider $0< a< 1000$, $0< b< 1000$. Is it true that the Euclidean algorithm will stop after at most 1) $14$; 2) $13$ steps? Send a solution

Problem 11. Let $a$ and $b$ be any integer numbers. Using the Euclidean algorithm, show how to find numbers $k$ and $l$ such that $ak +bl =GCD(a, b)$. Send a solution

Problem 12. Show that equation $ax+by=d$ has a solution in integer numbers if and only if $d⋮GCD(a,b)$. In particular, $GCD(a,b)$ is the smallest natural number that can be written as $ax+by$. Send a solution

Problem 13. Let $(x_0,y_0)$ be a solution of the following equation \begin{equation*} ax+by=d. \end{equation*} Let $a_0$ and $b_0$ be numbers such that $GCD(a,b)a_0=a$, $GCD(a,b)b_0=b$. Show that each solution of equation $ax+by=d$ has the following form \begin{equation*} x=x_0+b_0t,  y=y_0-a_0t, \end{equation*} where $t\in\mathbb Z$. Send a solution

Problem 14. Solve the following equations 1) $121x+91y=1$; 2) $-343x+119y=42$; 3) $111x-740y=11$. Send a solution

Problem 15. Draw angle $1^\circ$ using angles $32^\circ$ and $25^\circ$. Send a solution

Problem 16. Show that if $p$ is a prime number, then either $a$ is divisible by $p$ or we can find $x$ and $y$ such that $ax+py=1$. Send a solution

Problem 17. Let $p$ be a prime number. Show that if $ab⋮ p$, then either $a⋮ p$ or $b⋮ p$. Send a solution

Problem 18. Prove Fundamental theorem of arithmetic, Problem 16-3 from "Integer numbers 1". Send a solution

∆ Definition 3. The lowest common multiple of $a$ and $b$ is the smallest positive integer that is divisible by both $a$ and $b$. Notation: $LCM(a,b)$.

Problem 19. Show that for any $a$ and $b$ such that $a^2 + b^2 \ne0$, the following is true. 1) There exists unique $LCM(a,b)$. 2) $LCM(a,b)\cdot GCD(a,b)=ab$. Send a solution

Problem 20. Compute $LCM(12,15)$, $LCM(120, 45)$. Send a solution

Problem 21. * Find all pairs of numbers $x$ and $y$ such that $x^y=y^x$. Send a solution

Problem 22. * Consider a chocolate bar that has a form of an equilateral triangle with a side length $n$ and is divided by grooves into equilateral triangles with side lengths $1$. Two people play a game. A turn consists of breaking off a triangle from the bar along a groove, eating eat and passing the rest to the other player. The one who gets the last piece with a side length $1$ is the winner. If a player cannot make a move, the player loses. If both players play perfectly, who will win? Send a solution