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$
21
  • 3
    $\begingroup$ What does "102400...(2014 times)...002401" mean? It's not clear to me what should be the $...$. $\endgroup$
    – Surb
    Jul 27, 2018 at 9:23
  • 1
    $\begingroup$ It means that $1024$ and $2401$ have $2014\text{ '0'}s$ between them. $\endgroup$
    – DynamoBlaze
    Jul 27, 2018 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, 2018 at 9:28
  • 2
    $\begingroup$ @Servaes The strong Fermat test to base $2$ says it's composite. $\endgroup$
    – Daniel Fischer
    Jul 27, 2018 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, 2018 at 11:50

1 Answer 1

Reset to default
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$
2
  • $\begingroup$ How does this answer the question? It simply puts some weak constraint on the factors of $N$. $\endgroup$
    – Servaes
    Feb 7, 2019 at 8:18
  • $\begingroup$ It reduces the number of primes to be checked as the factor of N. $\endgroup$
    – sirous
    Feb 7, 2019 at 11:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .