# Which prime factors can a number of the form $1212…2121$ have?

The number $1212...2121$ with $n$ ones can be represented by $$z_n\ := \frac{2\times 100^n-35}{165}$$ or, substituting $m=2n-1$, by $$z_n\ :=\ \frac{4\times 10^m-7}{33}$$

It is easy to show that $2,3,5,7$ cannot be a factor of such a number. $11$ can be a factor, which can be shown by $11|121$. Obviously, greater prime factors $p$ must fulfil the equation $$4\times 10^m\equiv 7\ (\ mod\ p\ )$$ with some odd number $m$ or equivalent the equation $$2\times 100^n\equiv 35\ (\ mod\ p\ )$$

Is there an easy criterion, for which primes $p$, there is an $n$ (or an odd $m$), such that the equation holds ?

A necessary condition that $p\ge13$ occurs, is that $70$ is a quadratic residue modulo $p$. If $70$ is a quadratic residue modulo $p$ and $ord_{100}(p)=p-1$ additionally holds, $p$ will occur infinite many often.

• What might help : $$z_n-1=\frac{2\times 100^n-200}{165}=\frac{200(100^{n-1}-1)}{165}=\frac{120(100^{n-1}-1)}{99}$$ – Peter Sep 17 '15 at 18:51
• Since $100^n-1$ has "many" prime factors, the numbers $z_n$ tend to be prime, or at least to be coprime to, lets say $20!$. $z_n$ is prime for $n=4,6,22,70,314,700,799,990$ and PRP for $n=3905,7030$. Note that the number $314$, related to $\pi$, is member of the (probably) infinite sequence of $n's$, such that $z_n$ is prime. – Peter Sep 17 '15 at 19:10
• In addition to the necessary condition that $70$ is a QR mod $p$ won't it suffice that $\operatorname{ord}_{\Bbb{Z}_p^*}(100)=(p-1)/2$? After all, $100$ is a QR itself, and cannot really be a primitive root, but generating all the QRs suffices. Not sure how useful that (sufficient) order criterion really is, because it comes uncomfortably close to the problematics of the open Artin's conjecture. – Jyrki Lahtonen Sep 19 '15 at 16:00
• Or may be you meant that $10$ should be primitive! That has the well known reinterpretation that the period of decimals in the expansion of $1/p$ has length $p-1$. Anyway, barring a mistake in my calculation/programming $70$ is a QR modulo a prime $p$, iff $p$ is congruent to one of $$\{1, 3, 9, 11, 17, 23, 27, 31, 33, 37, 51, 53, 61, 69, 73, 81, 83, 93, 97, 99, 101, 111, 121, 127\}$$ or one of $$\{153, 159, 169, 179, 181, 183, 187, 197, 199, 207, 211, 219, 227, 229, 243, 247\}$$ or one of $$\{249, 253, 257, 263, 269, 271, 277, 279\}$$ modulo $280$ - 48 residue classes out of $\phi(280)=96$. – Jyrki Lahtonen Sep 19 '15 at 16:10

Not at first glance,

$$z_2=121=11^2$$ $$z_3=12121=17 \cdot 23 \cdot 31$$ $$z_4=1212121=1212121$$ $$z_5=121212121=83 \cdot 577 \cdot 2531$$

Then the next prime is $z_6$. I didn't find any other $z_n$ that are prime with $n \lt 16$.

Organizing the primes found so far, up to $n=16$, we have,

$11$,$17$,$23$,$31$,$83$,$263$...

The Case of $13$

For some reason, $13$ was the first prime missing from the above list. Using the divisibility rule for $13$ given here. I guess one could prove that, $z_n \mod 13$ can have values of $[1,4,5]$ that repeat in that order and nothing else.

Conclusion

As mentioned in the Wikipedia article, the general test for divisibility of a number is not explicitly known. Since the sequence of numbers you present is no different from a collection of random numbers, with respect to prime factorization, there is no reason to expect a closed form or "easy" solution to the problem.

• Indeed $13$ will never show up. – André Nicolas Sep 17 '15 at 20:18
• The numbers are far away from being random, even with respect to factorization (See my conditions for $p$ occuring as a factor). – Peter Sep 19 '15 at 14:45
• Zach, I don't really agree with your conclusion. IMHO this question should be seen contrasting the well known fact that every prime $p$ other than $2$ or $5$ occurs as a factor of an integer with decimal expansion consisting of a string of $1$s. – Jyrki Lahtonen Sep 19 '15 at 15:21
• @JyrkiLahtonen "Is there an easy criterion, for which primes $p$ , there is an $n$ (or an odd $m$ ), such that the equation holds?" I think you've misconstrued my statement a bit. My intent is to point out that there is no easy method to find all the primes that satisfy the equation. In fact, we don't even know all the primes, so the question is arguably ill-posed! – Zach466920 Sep 19 '15 at 16:25