2
$\begingroup$

Prove that each positive integer $n$: $ x = \displaystyle 10^{10^{10^n}}+10^{10^n}+10^n-1 $ is not prime.

This seems like a very difficult problem, any ideas at all?

I would like to use modular arithmetic and algebraic number theory. This is sort of inspired by: Gerry's Myerson's first proof (algebraic number theory).

Now here is my attempt:

If $x$ is NOT prime then:

$$x \equiv 0 \pmod{j}$$ for some $j$ right?

$$10^{10^{10^n}}+10^{10^n}+10^n \equiv 1 \pmod{j}$$

but here I get stuck on the LHS.

How can I use algebraic number theory?

$\endgroup$
  • 1
    $\begingroup$ Using the method which determines whether or not a number on base $10$ is divisible by $11$, you can see that if $n$ is even then this number is divisible by $11$. Now you're left with proving the above for odd values of $n$. $\endgroup$ – barak manos Feb 4 '15 at 15:13
  • $\begingroup$ @barakmanos I don't think that $\bmod 11$ works for even $n$. The two large terms in the expression put a "1" into the representation at digit positions of the same parity. By contrast I think the $\bmod 11$ argument is fine for odd $n$, for the same reason. $\endgroup$ – Joffan Feb 4 '15 at 15:21
  • $\begingroup$ @Joffan: Yep, that's correct. I initially wrote "odd", then changed it to "even". Now I can no longer change it, but whoever reads this comment-thread will know... Thanks. $\endgroup$ – barak manos Feb 4 '15 at 15:24
1
$\begingroup$

OK, so we can show that for $n>0$ $$a_n = 10^{10^{10^n}}+10^{10^n}+10^n-1$$

is divisible by $10^{2^k}+1$ where $2^k$ is the greatest power of $2$ that divides $n$, ie. $n=2^kd$, with $d$ odd

So, for $n$ odd, $k=0, 2^k=1$ and $n$ is divisible by $11$; for $n \equiv 2 \bmod 4$ , $k=1, 2^k=2$ and $n$ is divisible by $101$; for $n \equiv 4 \bmod 8$ , $k=2, 2^k=4$ and $n$ is divisible by $10001$, etc.

as a separate demonstration for the $n$ odd case, examining powers of $10, \bmod 11$: $$\begin{array}{c|c|c} \hline x & 10^x \bmod 11 \\ \hline 1 & 10 \\ \hline 2 & 1 \\ \hline 3 & 10 \\ \hline etc \\ \end{array}$$

Note that the higher power components are $10^\text{even}$
So when $n$ is odd, $a_n \equiv (1+1+10-1)\bmod 11 \equiv 0 \bmod 11$

For the general case, obviously $10^{2^k}-1 \equiv -2 \bmod (10^{2^k}+1)$ and we can see that $(10^{2^k}+1) \mid (10^{2(2^k)}-1)$ and also $(10^{2^k}+1) \mid (10^{2j(2^k)}-1)$ for $j\geq 1$,

So for example, $\overbrace{99999999999999}^{\text{14 9's}}\equiv -2 \bmod 101$

Now the two larger powers both have a high enough power of two in the exponent that they are each $\equiv 1 \bmod 10^{2^k}$ as above. So these add back $1$ each to the modular sum and the end result is that a suitable divisor can be found depending on the factors of $2$ in $n$.

So all $a_n$ are composite.

$\endgroup$
  • $\begingroup$ $10^3\equiv 12 \mod13$, $10^4\equiv 3 \mod13$, $10^5\equiv 4 \mod13$, $10^6\equiv 1 \mod13$ $\endgroup$ – Julián Aguirre Feb 5 '15 at 10:23
  • $\begingroup$ @JuliánAguirre - thanks - that's what I get for doing modular arithmetic in my head while driving... modified justification, proof for even numbers to pick up later... $\endgroup$ – Joffan Feb 5 '15 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.