Problem: Show that infinitely many members of the sequence $$1,11,111,1111,11111,11111, \dots$$ are divisible by $2^{2019}+1$.
I solved this problem using Euler's totient theorem. What I'm wondering is what, if any, other ways are there.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Your sequence is $(10^n-1)/9$, so what you need is $10^n \equiv 1 \bmod 9 (2^{2019}+1)$. After verifying that $\gcd(10, 9(2^{2019}+1))=1$, this follows from the fact that the multiplicative group of integers modulo $9(2^{2019}+1)$ is a finite group. (Euler's totient theorem gives the order of the group, but all you need is the fact that it is a finite group).
answered Apr 29, 2019 at 20:27
-
$\begingroup$ If I may ask though, what is the number of factors for $2^{2019}+1$? $\endgroup$– MikeApr 29, 2019 at 20:47
-
1$\begingroup$ @Mike It's easy to find some factors as it's one the form $2^{ab}+1$ ($3\cdot 673=2019$) and $x^{ab} + 1 = (x^a+1)(1-x^a + x^{2a}-\ldots+x^{a(b-1)})$. It therefore has atleast $5$ factors, but finding them all (which we need to know how many there are) requires factoring a number with $400$ digits, which is not that easy. $\endgroup$– WintherApr 29, 2019 at 21:07
-
$\begingroup$ Thanks @Winther. Which makes me wonder if there is an elegant trick for solving this. The exponent 2019 i.e., the current year makes me think this is doubles as a contest math problem, which have some sort of snappy solution. $\endgroup$– MikeApr 29, 2019 at 21:44
-
$\begingroup$ Oh, just show that infinitely many are divisible....Then yes it is easy to see from the above. For whatever reason I misread $\endgroup$– MikeApr 29, 2019 at 21:46