Some numbers are said to be *divisible* by certain divisors. By this, we mean that they are *exactly divisible*, in other words, with zero remainder.
For example, 8 is divisible by 2, which means that 8 divided by 2 gives a whole number (4) and leaves remainder 0. However, 8 is not divisible by 3, since that would give a quotient 2 and a remainder 2 (8 = 2·3 + 2)
The term "divisible" can lead to confusion if you think in terms of numbers with decimal positions. If we divide 3 by 2, you can certainly say that the result is 1.5, so that you can think that 3 is divisible by 2 because we have been able to perform such division. However, this is not what we mean by divisible here.
For long I have been using an invented notation for divisibility. You can ignore this, of course, but I will share this notation here just in case you find it useful.
For example, if I want to say that 10 is divisible by 2, I write that 10 is div-2. It is just a shorthand. There are more formal ways to say the same, for example by using modular arithmetic. To say that 10 is div-2 would be the same as to write that 10 ≡ 2 (mod 2). But this is out of the topic of the present study. For a simple algebra introduction I prefer the use of div-d.
Let the divisor be d=2. Which numbers are div-2? Clearly, 2, 4, 6, 8, 10, etc. They are called *even numbers*. Upon division by 2, an even number always has r=0.
The rest of numbers, 1, 3, 5, 7, 9, 11, etc are called *odd* numbers and they are not div-2. If you try to divided any odd number by 2, you will always get r=1.
Let n be an generic integer number. Then, the expression 2n encapsulates all even numbers. Give specific values for n, like n = 1, 2, 3, 4, etc and we will get 2n = 2, 4, 6, 8, etc.
Can we do a similar thing for odd numbers? Yes. We can write 2n+1, which for n = 1, 2, 3, 4, etc give 2n+1 = 3, 5, 7, 9, etc. Alternatively, we can write 2n -1 which will give 1, 3, 5, 7, etc. You may think that the second expression, 2n-1, is better because it outputs odd numbers beginning from 1 instead of 3, but you can give to n whatever integer value, so for n = 0, 1, 2, etc we get 2n+1= 1, 3, 5, 7, etc while 2n-1 = -1, 1, 3, 5, etc. Bot expressions 2n+1 and 2n-1 are perfectly valid as generic odd numbers.
Notice how any odd dividend D can be written as D = q·d + r, in this case D = q·2 + 1.
For the expression 2n-1 we need to express the remainder as a negative number, which is something we have not done before, but it is perfectly possible! Usually, when we divided, we seek quotients such that the multiplication q·d gives a value smaller than D, so that the remainder is a positive quantity (there are apples not shared out among people). However, we coul perfectly use a quotient q such that q·d gives a number greater than D.
For example, we have 14 apples to be shared among 5 people. On our usual approach we would propose q=2, so that 14 = 2·5 +4, having remainder r=4. But another choice is to get q=3, and then 14 = 3·5 -1, which means that we "give" (in this case promise) 3 apples to each person, but instead of having surplus apples, we end up owing an apple to one of the persons. This is the meaning of a negative remainder.
So odd numbers written as 2n+1 use positive r=1 while 2n-1 use negative r=-1.
Let's consider now d = 3. The numbers 3, 6, 9, 12, 15, etc are all div-3. All of them give r=0 upon division by 3.
What about 1, 4, 7, 10, 13, etc? They all give r=1 upon division by 3, so they can be generically written as 3n+1, or alternatively by 3n-2 if you prefer to use a negative remainder.
Similarly, numbers 2, 5, 8, 11, 14, etc all live r=2 upon division by 3, so they can be written as 3n+2. Alternatively, you can use 3n-1 if you use r=-1.
Notice how the expression D = q·d + r is appearing all the time!
Euler here proceeds for numbers which are div-4.
4,8,12,16, etc are all div-4, and they can be written as 4n.
1,5,9,13,17, etc can be written as 4n+1 (or 4n-3).
You may ask, why not -11, -7, -3, 1, 5, 9, 13, etc? Of course! Feel free to include negative numbers as well!
Surely now you see how this all goes. For d=4, we still can write those who are 4n+2 (2,6,10, etc) and those who are 4n+3 (3,7,11, etc).
All integer numbers can be covered by the following four expressions:
4n + 0
4n + 1
4n + 2
4n + 3 .
But all integer numbers were covered as well by
3n + 0
3n + 1
3n + 2 .
And they also got covered by
2n + 0
2n + 1 .
And also by
1n + 0 .
It will not be a surprise to see that for d=5, all numbers div-5 are 5n, and that all integers can be covered by the set of expressions
5n + 0
5n + 1
5n + 2
5n + 3
5n + 4
It is easy to see how to generalise this for any divisor.
Take a number, for example, 60. We factorise it in prime factors as 60 = 2·2·3·5. This clearly means that 60 is div-2, div-3 and div-5.
For if we divided 60 by 5, we get rid of the 5 and obtain 2·2·3=12. If we divided 60 by 3, we have left 2·2·5 = 20. And so on.
In general, then, a number which has a factor a will always be div-a. This may sound trivial to you now, but I assure you that trivial this is not.
Expanding the previous point, we can say that if a number n has two factors a and b, then n is not only div-a and div-b, but also div-(ab).
Using the example n=60 again, we see that 60 is div-(2·3) or just div-6. It is also div-4, div-10, div-15 and why not, also div-12, div-30, div-20 or div-60. Why restrict this to two factors only?
We have seen how much power we obtain when we represent a number by its prime factorisation. When we have such factorisation, it is very easy to see whether the number is divisible by any number.
It is evident that every number n is both div-1 and div-n, but it is of no interest, as we already discussed, to consider 1 as a factor, and it is not more interesting to consider n itself as a factor.
What is interesting here is that when a number is *only* div-1 and div-n, then it is a prime number.
Composite numbers, on the other hand, will have at least one more divisor between 1 and the number itself.
Remember that Ω(n) will tell you how many divisors in total a number n has, while ω(n) will tell you how many distinct divisors a number n has. Both prime omega functions ω and Ω are very important.
You have seen how number is 0 is always a weird number with respect to division. See how 0 is div-a for every integer a except a=0. For example, see how 0 is div-2, since 0 divided by 2 gives a whole number (0 again). .Same for 3 or 4 or every integer except 0. Don't be tempted to divided 0 by 0.