22
$\begingroup$

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.

Please help.

$\endgroup$
  • 3
    $\begingroup$ What does "102400...(2014 times)...002401" mean? It's not clear to me what should be the $...$. $\endgroup$ – Surb Jul 27 '18 at 9:23
  • 1
    $\begingroup$ It means that $1024$ and $2401$ have $2014\text{ '0'}s$ between them. $\endgroup$ – MalayTheDynamo Jul 27 '18 at 9:24
  • 2
    $\begingroup$ Am I right in thinking that your number has $2022$ digits of which $2016$ are zero? $\endgroup$ – Mark Bennet Jul 27 '18 at 9:28
  • 2
    $\begingroup$ @Servaes The strong Fermat test to base $2$ says it's composite. $\endgroup$ – Daniel Fischer Jul 27 '18 at 11:24
  • 4
    $\begingroup$ @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.) $\endgroup$ – Daniel Fischer Jul 27 '18 at 11:50
1
$\begingroup$

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.

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

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.