# Proving $10240…02401$ composite

I got this question recently, and have been unable to solve it.

Prove that $1024\underbrace{00 \ldots\ldots 00}_{2014 \text{ times}}2401$ is composite.

I have two different ways in mind.

First is $7^4+400(2^2\cdot10^{504})^4$, which looks like Sophie Germain, but I'm not sure what to do with the $400$. Another thought is that this is almost a palindrome, with the order of just two digits interchanged. I'm not sure where to go from there, and if it'd provide any results, but it seems interesting nonetheless.

• What does "102400...(2014 times)...002401" mean? It's not clear to me what should be the $...$. – Surb Jul 27 '18 at 9:23
• It means that $1024$ and $2401$ have $2014\text{ '0'}s$ between them. – DynamoBlaze Jul 27 '18 at 9:24
• Am I right in thinking that your number has $2022$ digits of which $2016$ are zero? – Mark Bennet Jul 27 '18 at 9:28
• @Servaes The strong Fermat test to base $2$ says it's composite. – Daniel Fischer Jul 27 '18 at 11:24
• @Servaes Write $n-1 = 2^k\cdot m$ with $m$ odd, and then $$a^{n-1} - 1 = (a^m - 1)\prod_{\kappa = 0}^{k-1}\bigl(a^{2^{\kappa} m} + 1\bigr)$$ where $1 < a < n-1$. Then $n$ is a strong Fermat probable prime if $n$ divides one of the factors of the product, i.e. $a^m \equiv 1 \pmod{n}$ or there is a $\kappa \in \{0,\dotsc, k-1\}$ such that $a^{2^{\kappa}m} \equiv -1\pmod{n}$. That's the test Miller-Rabin is composed of. In this case, $a = 2$ shows it's composite. (Actually already the ordinary Fermat test shows that here.) – Daniel Fischer Jul 27 '18 at 11:50

The method introduced in this modification is for reduction of volume of calculations.

Let's start with a simple example; consider number $$N=1024002401=1670477\times 613$$. We may write:

$$N=2^{10}.10^6+24.10^2 +1=2^3.10^2(2^7.10^4+3)+1$$

$$2^7.10^4+3=1280003 ≡59 \mod (613)$$

$$N=2^3.10^2(613 k + 59)+1=800\times 613\times k +800 \times 59 +1$$

Let $$800\times 613 =a$$ and $$800\times 59 +1 =b$$

$$(a, b)=613$$

Now suppose we do not know that $$p=613$$ and $$r=59$$ in following relation:

$$(a, b)=(800 p, 800 r+1)=p$$

$$a=800 r +1$$ gives infinite numbers which its factors may be candidates for a factor of a number like ($$N=2^{\alpha}.10^{\beta}+3^{\gamma}$$).

For example giving r numerous values we find that for $$r=59$$ we get $$800\times 59+1=47201=7\times 11\times 613$$. Each of theses three factors can be the candidate for p to be tried to find the factor of N. For $$N=2^{10}.10^{2018}+7^4$$ we may write:

$$N=2^{10}.10^{2018}+7^4=2^3.10^2(2^7.10^{2016}+3)+1$$

$$2^7.10^{2016}+3≡ r\ mod (p)= k.p +r$$

$$N=800(k.p+r)+1=800p.k+800r +1$$

Now values for $$r$$ in $$(800 r +1)$$ give numbers their factors can be checked as a primes factor of N.

• How does this answer the question? It simply puts some weak constraint on the factors of $N$. – Servaes Feb 7 '19 at 8:18
• It reduces the number of primes to be checked as the factor of N. – sirous Feb 7 '19 at 11:18