整数整除的基本性质

This is an introduction into number theory. Many people try to define it as "arithmetic of integers", but we aren't going to define and restrict the area of mathematics it covers. Instead, we just intend to explore the integers and their properties for now, from an olympiad perspective.

Divisibility

This is the most basic part of number theory. Let's say, $a$ divides $b$ if $b$ leaves a remainder of $0$ when divided by $a$. We say that, $b$ is divisible by $a$. Here, $a$ is the divisor and $b$ is the multiple. It is usually denoted by $a|b$, or some authors denote it by $b\vdots a$. But here, we will go with the first notation.

Example $2$ is a divisor of $8$ and $10$ is a multiple of $5$, so $2|8$ and $10\vdots5$.

Usually, by divisor, we mean only positive divisors. Because divisors can be negative too, but unless stated explicitly, a divisor means a positive divisor. Now, if $a$ divides $b$, then the result of their division is called quotient and this is certainly an integer. Thus, if $\dfrac{b}{a}=k$, then $k$ is the quotient.

A number $n$ is called prime if it has exactly two distinct divisors: $1$, and $n$ itself. A number greater than $1$ which isn't prime is composite, in other words a positive integer $n$ is composite if a positive integer greater than $1$ divides $n$.

You should guess already. $2$ is the only even prime. Think on why it is so.

Now, if $a|b$, we can say that $b$ must be greater than or equal to $a$, since everything that's a part of $a$ must be in $b$ too. That is, $b\geq a$. We should actually write $|b|\geq|a|$, where $|x|$ is the absolute value of $x$. Because they can be negative integers too. There is one case though where this fails. That is, when $b=0$. One can say, $a|b$ and $|b|<|a|$ is possible only in one case when $b=0$.

If $a|b$ and $a|c$, can you say that $a|b+c$? What about $a|b-c$? Actually both are true, and they can be generalized. If $a|b$ and $a|c$, then $a|bx+cy$ for any integers $x,y$. Important special cases are: If $a|b$, $a|b\pm aq$ for any integer $q$.

Let's prove it formally. If $a|b$ then $b=ak$ and similarly $c=al$ if $a|c$. Then $$bx+cy=akx+aly=a(kx+ly)$$ which is certainly divisible by $a$.

Problems

$1.$ Find all positive integer $n$ which satisfies $8n+9|12n+5$.

First let's think on how to approach. It is obvious we need to cancel out the $n$ on the right side by any means. Think yourself how you can do it.

Solution: $8n+9|3(8n+9)=24n+27$, and $8n+9|2(12n+5)=24n+10$. Thus, $8n+9|24n+28-(24n+10)=17$. $17$ has only two divisors, namely $1$ and $17$. $8n+9=1$ doesn't have any solution in positive integers. $8n+9=17$ yields $n=1$.

$2.$ Find the largest positive integer $x$ so that $x+25$ divides $x^2+25$.

Solution 1: $x+25|x(x+25)=x^2+25x$, and from the condition, we have $x+25|x^2+25$. If we subtract, we have $x+25|25x-25$. Again we need to rule out $x$ in a same manner. $x+25|25(x+25)=25x+625$ and $x+25|25x-25$. Subtract again and we get $x+25|25x+625-(25x-25)=650$. Now, $x+25\leq 650$ and so $x=625$ is the solution.

Note: we could have written $x+25|25-25x$ too when we subtracted. But that wouldn't matter in this case. Because we could have just added to $25x+625$ instead of subtracting and gain the same result.

The following solution is a crafty one. But you have to know the following identity for that: $$a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+\ldots+b^{n-1}\right)$$ A special case is $a^2-b^2=(a+b)(a-b)$.

Solution 2: We have $x+25|x^2-25^2$ or $x+25|x^2-625$. Thus, $x+25|x^2+25-(x^2-625)=650$ and the same result.

Questions

We say an integer $d \ne 0$ divides an integer $n$ if and only if there exists an integer $c$ such that $n = c \cdot d$. In other words, $\frac{n}{d}$ is an integer. We can also say $d$ is a divisor of $n$, or $n$ is divisible by $d$. We must exclude $d = 0$ because unless we are studying wheel theory, division by $0$ is undefined. We can write $d$ divides $n$ as $d | n$, and we can write $d$ does not divide $n$ as $d \nmid n$.

Most proofs for divisibility properties resort back to this definition. For example, to prove the obvious statement $a | a$, we must find an integer $c$ such that $a = c \cdot a$. Clearly, $c =$ 1.

For a simple counterexample to the second statement, note that $4 | 12$ and $6 | 12$, but obviously $24 \nmid 12$. To prove the first statement, note that $a | b$ means that there exists an integer $m$ such that $b = m \cdot a$, and $b | c$ means that there exists an integer $n$ such that $c = n \cdot b$. Multiplying the first equation by $n$ gives $m \cdot n \cdot a = b \cdot n = c$. Since $c = (m \cdot n) \cdot a$, we see that $a | c$, as desired. Try proving the third statement on your own!

For a simple counterexample to the last statement, note that $1 | 4$ and $2 | 4$, but $3 \nmid 4$. You should try proving the first two properties on your own! Together, these two properties tell us that divisibility still holds after a linear combination. That is, given some set of numbers that are all divisible by $d$, then the sum or difference of any amount of those numbers will yield a number also divisible by $d$. Beware, though! The converse is not necessarily true. If $d \nmid m$ and $d \nmid n$, then it is not guaranteed that $d \nmid (m \pm n)$. For example, $2 \nmid 1$ and $2\nmid 3$, but clearly $2 \mid 4$.

Now, let's try to put some bounds on what numbers can divide another number.

We can revise the statement to the following: If $d | n$ and $n \ne 0$, then $|d| \le |n|$. This will always hold. Note that $n = 0$ somewhat of a special case since for any integer $d \ne 0$, $d | 0$ because $0 = 0 \cdot d$. That is, $0$ has infinitely many divisors. A consequence of this is that if $d | n$ for infinitely many integers $d$, then $n = 0$. To prove this, suppose the contrary that $n \ne 0$. Then our condition guarantees that there exists a $d > n$, which contradicts $d \le n$, a necessary condition for $d | n$. Therefore we must have $n = 0$.

You can now prove the following: If $m | n$ and $n | m$, then $m = \pm n$.

Finally, it is worth noting that you can exploit algebraic properties and factorizations to prove divisibility. In particular, since $a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b + \cdots + ab^{n-2} + b^{n-1})$, we have $(a-b) | (a^n - b^n)$ for any integers $a, b$ and positive integer $n$ provided that $a \ne b$. Similarly, you can easily show that $(a+b) | (a^n + b^n)$ for any integers $a, b$ and positive odd integer $n$, provided that $a \ne -b$.

Without using congruence or brute force methods, prove that $2^{32}+1$ is divisible by $641$.

If $x,y$ are integers and $a$ divides both $b$ and $c$, prove that $a$ divides any linear combination of $b$ and $c$ i.e. $a|bx+cy$.