12*. How many integers are there that are less than the number 56700000 and coprime with it?
12. The problem is very close to the previous one. The factorization of the number 56700000 is $56700000=2^{5} \cdot 3^{4} \cdot 5^{5} \cdot 7$; thus, the problem reduces to determining how many numbers less than 56700000 are not divisible by 2, 3, 5, or 7.

Let's list all numbers from 1 to 56700000. We will strike out all numbers divisible by 2 (their number is $\frac{1}{2} \cdot 56700000=28350000$); all numbers divisible by 3 (their number is $\left.\frac{1}{3} \cdot 56700000=18900000\right)$; all numbers divisible by 5 (their number is $\frac{1}{5} \cdot 56700000=11340000$); all numbers divisible by 7 (their number is $\frac{1}{7} \cdot 56700000=8100000$). The total number of all these numbers is $28350000+18900000+11340000+8100000=$

$=66690000$.

But among these 66690000 numbers, there are: $\frac{1}{2 \cdot 3} \cdot 56700000=9450000$ numbers divisible by 2 and 3; $\frac{1}{2 \cdot 5} \cdot 56700000=5670000$ numbers divisible by 2 and 5; $\frac{1}{2 \cdot 7} \cdot 56700000=4050000$ numbers divisible by 2 and 7; $\frac{1}{3 \cdot 5} \cdot 56700000=3780000$ numbers divisible by 3 and 5; $\frac{1}{3 \cdot 7} \cdot 56700000=2700000$ numbers divisible by 3 and 7; $\frac{1}{5 \cdot 7} \cdot 56700000=1620000$ numbers divisible by 5 and 7.

All these numbers are counted twice in the sum of all numbers divisible by 2, or 3, or 5, or 7. Therefore, the total number of these numbers, equal to

$$
\begin{gathered}
9450000+5670000+4050000+3780000+ \\
+2700000+1620000=27270000
\end{gathered}
$$

must be subtracted from the sum obtained above:

$$
66690000-27270000=39420000
$$

In the difference $66690000-27270000$, obviously, all numbers divisible by only one of the factors 2, 3, 5, and 7, and all numbers divisible by two of these factors (the first are counted once in the minuend; the second are counted twice in the minuend and once in the subtrahend) are included once. Now let's determine how any number divisible by three of these factors, for example, by 2, 3, and 5, is counted in this difference. This number is counted three times in the minuend (among the numbers divisible by 2, among the numbers divisible by 3, and among the numbers divisible by 5) and three times in the subtrahend (among the numbers divisible by 2 and 3, among the numbers divisible by 2 and 5, and among the numbers divisible by 3 and 5). Therefore, all numbers divisible by any three of the four factors 2, 3, 5, and 7 are not counted at all in our difference, and we must add to the difference the total number of all such numbers. The total number of these numbers (not exceeding 56700000) is obviously

$$
\begin{aligned}
& \frac{1}{2 \cdot 3 \cdot 5} \cdot 56700000+\frac{1}{2 \cdot 3 \cdot 7} \cdot 56700000+\frac{1}{2 \cdot 5 \cdot 7} \cdot 56700000+ \\
&+\frac{1}{3 \cdot 5 \cdot 7} \cdot 56700000= \\
&=1890000+1350000+810000+540000=4590000
\end{aligned}
$$

Thus, we get:

$$
66690000-27270000+4590000=44010000
$$

In the expression $66690000-27270000+4590000$, all numbers divisible by one of the factors 2, 3, 5, and 7; by two of these factors; and by three of these factors are counted once. Now let's determine how numbers divisible by 2, 3, 5, and 7 are counted in this expression. They are obviously counted four times in the first term 66690000 (as divisible by 2, 3, 5, and 7); six times in the second term 27270000 (as divisible by 2 and 3; 2 and 5; 2 and 7; 3 and 5; 3 and 7; 5 and 7); and four times in the last term (as divisible by 2, 3, and 5; 2, 3, and 7; 2, 5, and 7; 3, 5, and 7). Therefore, these numbers are counted in our expression $4-6+4=2$ times, and their number, equal to $\frac{1}{2 \cdot 3 \cdot 5 \cdot 7} \cdot 56700000=270000$, must be subtracted:

$66690000-27270000+4590000-270000=43740000$.

Thus, from 1 to 56700000, there are 43740000 numbers divisible by at least one of the factors 2, 3, 5, or 7. Therefore, the number of numbers not divisible by any of these factors (coprime with the number 56700000) is

$$
56700000-43740000=12960000
$$

Note. It can be shown in the same way that if the factorization of the number $N$ into prime factors is

$$
N=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} p_{3}^{\alpha_{3}} \ldots p_{k}^{\alpha_{k}}
$$

then the number $\varphi(N)$ of numbers less than $N$ and coprime with it is

$$
\begin{aligned}
\varphi(N)= & N-\frac{N}{p_{1}}-\frac{N}{p_{2}}-\ldots-\frac{N}{p_{k}}+\frac{N}{p_{1} p_{2}}+\frac{N}{p_{2} p_{3}}+\ldots+\frac{N}{p_{k-1} p_{k}}- \\
& -\frac{N}{p_{1} p_{2} p_{3}}-\ldots-\frac{N}{p_{k-2} p_{k-1} p_{k}}+\ldots+(-1)^{k} \frac{N}{p_{1} p_{2} \ldots p_{k}}= \\
= & N\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right)\left(1-\frac{1}{p_{3}}\right) \ldots\left(1-\frac{1}{p_{k}}\right)
\end{aligned}
$$

(see the note to the solution of problem 11b).