Задача за делимост

[Гост]

Нека М=1010101…01, където цифрата 1 се среща k пъти. Намерете най-малката стойност на k, за която 1001001001001 дели М.

[martin123456]

Лесно се вижда,че [tex]M=\frac{10^{2k}-1}{99}[/tex] и [tex]A=\frac{10^{15}-1}{3^3.37}[/tex].
Търсим min k, [tex]A|M[/tex].
Нека частното е [tex]s\in\mathbb{N}[/tex].
[tex]\Rightarrow (10^{2k}-1)37.3=s.11(10^{15}-1)[/tex].
Знаем, че [tex]gcd(10^{2k}-1, 10^{15}-1)=10^{gcd(k,15)}-1=10^d-1[/tex], нека [tex]10^{2k}-1=(10^d-1)x_1, 10^{15}-1=(10^d-1)x_2, gcd(x_1,x_2)=1[/tex].
Уравнението става [tex]37.3x_1=11.s.x_2 \Rightarrow x_2|37\Rightarrow x_2 \in \{1,37\}[/tex].
Случай 1: [tex]x_2=1\Rightarrow d=15[/tex]. [tex]10^{2k}-1=(10^{15}-1)x_1[/tex]. Значи [tex]15|k\Rightarrow k\ge 15[/tex]. При [tex]k=15[/tex] имаме решение.
Случай 2: [tex]x_2=37\Rightarrow 10^{15}-1=(10^d-1)37[/tex], което е невъзможно.