Wielokrotności liczb nieparzystych

[mol_ksiazkowy]

Czy każda liczba nieparzysta ma jakąs wielokrotność mającą same cyfry nieparzyste ?
Jeśli nie to wskazać najmniejszą która taka nie jest
Przykłady \(\displaystyle{ 357 = 21 \cdot 17 \ \ 515 = 5 \cdot 103 \ \ 101 \cdot 17 = 1717}\) itd.

[hannahannah]

Jeśli \(\displaystyle{ (n,5)=1}\), to łatwo pokazać, że tak:

Niech \(\displaystyle{ r}\) będzie rzędem multiplikatywnym \(\displaystyle{ 10}\) modulo \(\displaystyle{ n}\). Wówczas \(\displaystyle{ n|10^r-1}\), ale \(\displaystyle{ 10^r-1}\) ma jedynie dziewiątki w zapisie dziesiętnym. Argument można podrasować tak, że \(\displaystyle{ 9n|10^s-1}\) dla pewnego \(\displaystyle{ s}\). Czyli każda liczba nieparzysta nie kończąca się piątką jest dzielnikiem liczby mającej same jedynki w zapisie. Przypadek \(\displaystyle{ 5|n}\) wydaje się znacznie trudniejszy.

[marcin7Cd]

Udowodnię następujący lemat: Jeśli da się dla \(\displaystyle{ 5^m}\), to da się dla \(\displaystyle{ n5^m}\), gdzie \(\displaystyle{ NWD(n,10)=1}\).
Dowód: Niech \(\displaystyle{ a}\) będzie wielokrotnością \(\displaystyle{ 5^m}\) o nieparzystych cyfrach. Załóżmy, że \(\displaystyle{ a}\) ma \(\displaystyle{ x}\) cyfr. \(\displaystyle{ n|\frac{10^{\varphi(n \cdot (10^x-1))}-1}{10^x-1}=10...010...010...01}\), pomiędzy jedynkami jest \(\displaystyle{ x}\) zer. liczba \(\displaystyle{ 5^m \cdot \frac{10^{\varphi(n \cdot (10^x-1))}}{10^x-1}}\) ma wszystkie cyfry nieparzyste i dzieli się przez \(\displaystyle{ n5^m}\), co kończy dowód lematu.

Teraz udowodnię za pomocą indukcji, że istnieje taka wielokrotność \(\displaystyle{ 5^m}\) mająca \(\displaystyle{ m}\) cyfr. Dla \(\displaystyle{ m=1}\) teza oczywiście zachodzi. Załóżmy indukcyjnie, że zachodzi dla \(\displaystyle{ 5^m}\). Wtedy istnieje taka wielokrotność \(\displaystyle{ a}\) liczby \(\displaystyle{ 5^m}\) o nieparzystych \(\displaystyle{ m}\) cyfrach. Rozważmy liczby \(\displaystyle{ k \cdot 10^m+a}\), gdzie \(\displaystyle{ k \in \left\{ 1,3,5,7,9\right\}}\) Wszystkie one są różne modulo \(\displaystyle{ 5^{m+1}}\), bo jeśli \(\displaystyle{ k\cdot 10^m+a \equiv l \cdot 10^m +a \pmod{5^{m+1}}}\), to wtedy \(\displaystyle{ 5^{m+1}|(k-l)\cdot 2^m \cdot 5^m \Rightarrow 5|k-l}\), co dla \(\displaystyle{ k,l \in\left\{1,3,5,7,9 \right\}}\) oznacza \(\displaystyle{ k=l}\). Któraś z tych liczb musi być podzielna przez \(\displaystyle{ 5^{m+1}}\) ,a każda cyfra jest nieparzysta (jest ich \(\displaystyle{ m+1}\) ) , co kończy dowód indukcyjny.
Łącząc ten fakt z lematem otrzymuje twierdzącą odpowiedź.