Non-squarefree numbers of the form $10^n + 1$

Question

Consider numbers of the form $10^k + 1$. We can look at the prime factorisation of these numbers and note that the smallest such number that has a repeated prime factor is $10^{11} + 1 = 11^2\cdot{}23\cdot{}4093\cdot{}8779$. We can use this to form a number of the form $a = a_1a_2\dots{}a_ka_1a_2\dots{}a_k$ such that $a$ is a perfect square (the smallest such number is $1322314049613223140496 = 36363636364^2$).

The next smallest number of the form $10^{k} + 1$ with a squared prime factor is $10^{21} + 1 = 7^2\cdot{}11\cdot{}13\cdot{}127\cdot{}2689\cdot{}459691\cdot{}909091$ which can be used to form perfect squares with repeated digits in a similar fashion. Following that comes $10^{33} + 1$, again divisible by $121$ and then $10^{39} + 1$, divisible by $169$.

OEIS contains the sequence A086981, for which $s(n)$ comprises the smallest value of $k$ for which $10^k + 1$ is divisible by $p_n^2$, where $p_n$ is the $n$th prime number. Obviously numbers of our special form are not divisible by $2, 3$, or $5$ so the sequence starts $0, 0, 0, 21, 11, 39$.

For some primes $> 5$, the sequence contains a zero, indicating (quoting) no such $k$ exists. The first entry that is not trivially zero is the $11^{\mathrm{th}}$, corresponding to 31. Following that are 37, 41 and 43. The next entry is $1081$ and indeed $10^{1081} + 1$ is divisible by 2209.

Does the "no such $k$" wording mean that necessarily no such $k$ exists, or that no known $k$ exists? I have checked for e.g. divisibility by $41^2$ up to $k$ = several million just for fun.

Answer 1

the first thing that comes to mind: for a prime $q \equiv 3 \pmod 4$ we know $-1$ is not a quadratic residue. Therefore, if $10$ is a quadratic residue, it is impossible to have $10^k \equiv -1 \pmod q$ Let me work up some examples. Meanwhile, $3, 27, 31, 39 \pmod {40} $ primes make the task impossible

There are other ways for $10$ to fail to be a primitive root $\pmod p.$ For instance, the powers of $10$ taken $\pmod {41}$ are, in order $1, 10, 18, 16, 37, 1, 10, 18, 16, 37,... $ forever. That is, although $-1$ certainly is a residue $\pmod {41},$ we get the premature $10^5 \equiv 1 \pmod {41},$ only five values occur in this subgroup (of the multiplicative group which has $40$ elements)

Anyway, it was not necessary to check $p=41$ for large exponents. Just check exponents up to $p-2$ and check for an early 1.

Up to 335, the primes that are ruled out by these methods are

three mod 4:

$$ 3, 31, 43, 67, 71, 79, 83, 107, 151, 163, 191, 199, 227, 239, 271, 283, 307, 311, $$

one mod 4

$$ 37, 41, 53, 173, 277, 317, $$

Answer 2

The question is really whether it is possible for $10^k+1$ to be divisible by $p$. See Will Jagy's answer for more information on that. If such an integer $k$ exists there will be one in the range $0<k\le (p-1)/2$, so you never need to run the tests longer than that.

The point I want to make is that if $p\mid 10^k+1$ for some integer $k>0$ and a prime $p>5$, then $p^2\mid 10^{kp}+1$. This is because we have the factorization $$10^{kp}+1=(10^k+1)(10^{k(p-1)}-10^{k(p-2)}+10^{k(p-3)}-\cdots+10^{2k}-10^k+1).$$ Here the latter factor is also divisible by $p$ because all the terms leave remainder $+1$ when divided by $p$, and there are $p$ of them.

This is the inductive step in the so called lifting the exponent lemma.

This means that divisibility by $p^2$ is not the real obstruction. If you can make $10^k+1$ divisible by $p$, you can make it divisible by $p^2$, $p^3$ et cetera.

Answer 3

We can test whether $p|10^n+1$ for some natural number $n$ and any given prime $p$ using a result from the theory of modular arithmetic.

Let $m$ be the largest odd number dividing $p-1$. Then $10^m\bmod p$ will be either (a) $\equiv1$ or (b) a residue that becomes $\equiv1$ upon squaring it one or more times. In case (b) the squaring process identifies a solution (not always minimal) for $p|10^n+1$, because $-1$ will always occur immediately before $+1$ during the squaring process; but in case (a) we would need $m=2^{k\ge1}n$ which is contradictory because $m$ is chosen odd.

For instance, if we try $p=47$ then $m=23$, and we use the squaring and multiplication technique to render $10^{23}\bmod 47$:

$10^2\equiv6$

$10^4\equiv6^2\equiv36$

$10^5\equiv36×10\equiv31$

$10^{10}\equiv31^2\equiv21$

$10^{11}\equiv21×10\equiv22$

$10^{22}\equiv22^2\equiv14$

$10^{23}\equiv14×10\equiv\color{blue}{46}$

from which we infer that case (b) applies and thus $47$ divides $10^n+1$ for some $n$. In this case that turns out to be $n=23$ itself because $46\equiv-1\bmod47$. Then by the exponential lifting process we know that $10^{47×23}+1=10^{1081}+1$ will be divisible by $47^2$.