6
$\begingroup$

I need to find a prime factor, $p$, of $1002004008016032$ such that $p \gt 250000$. Now this is a very large number and I know it would be stupid of me to factorize such a large number into its prime factors . Any help how I can solve this ?

$\endgroup$
  • 2
    $\begingroup$ $2^5\times 3^2\times 7\times 109^2\times 167\times 250501$ $\endgroup$ – polfosol Dec 31 '16 at 18:03
  • $\begingroup$ How did you figure out such nasty factors :) $\endgroup$ – user366398 Jan 1 '17 at 0:25
  • $\begingroup$ Go here $\longrightarrow$ alpertron.com.ar/ECM.HTM It is a calculator and strictly works for integers. When a decimal is put, it will round the result to the nearest integer. When given an equation or inequality, it will return $-1$ if true and $0$ if false. It also has many other functions you can learn :) $\endgroup$ – Mr Pie Mar 30 '18 at 18:26
19
+50
$\begingroup$

$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+xy^{n-2}+y^{n-1})$

Taking $x=10^3,y=2$, we get

$1002004008016032=x^5+x^4y+x^3y^2+x^2y^3+xy^4+y^5=\frac{x^6-y^6}{x-y}$

Also,

$\frac{x^6-y^6}{x-y} = (x+y)(x^2+xy+y^2)(x^2-xy+y^2)$

=$1002\times1002004\times998004 = 1002\times16\times250501\times249501$

Hence, the prime number , $p\gt250000$ is $250501$

$\endgroup$
  • 5
    $\begingroup$ If there exist "nerd-answers" at all: then this is one... :-) $\endgroup$ – Gottfried Helms Oct 17 '19 at 6:43
  • 2
    $\begingroup$ @GottfriedHelms And now I am having so much fun asking Wolfram to factor expressions of the form $\frac{x^n-y^n}{x-y}$ $\endgroup$ – CopyPasteIt Oct 21 '19 at 12:14
  • 4
    $\begingroup$ @CopyPasteIt - see my joy on analyzing this in this essay on my webspace go.helms-net.de/math/expdioph/CyclicSubgroups_work.pdf Perhaps you like that approach as well... :) $\endgroup$ – Gottfried Helms Oct 21 '19 at 12:18
0
$\begingroup$

The OP was looking for any help. If all you have as an aid is access to the Python programming language, you can code this:

L = 1002004008016032
b = 250001

while True:
    r = L % b
    if r == 0:
        print(b)
        break
    b = b + 1

for n in range(2,int(b**.5)+1):
    if b % n == 0:
        print(b, 'is not a prime')
        raise SystemExit

print(b, 'is a prime')
raise SystemExit

giving the output

250501
250501 is a prime

ANS: $250501$

If it turned out that $250501$ was not a prime, you would have to edit the while loop, changing it to

while True:
    r = L % b
    if r == 0 and b != 250501:
        print(b)
        break
    b = b + 1

and then rerun the program to get the next factor candidate.

It is possible that many reruns would be required to find the answer using this technique, but the code can also be easily modified with a one-run requirement.

$\endgroup$
  • 1
    $\begingroup$ For a simpler programmatic solution, just type factor 1002004008016032 in a Linux/Unix terminal $\endgroup$ – Tobias Kildetoft Oct 21 '19 at 11:58
  • $\begingroup$ @TobiasKildetoft Yes, and there is also Wolfram. But I was interested in the underlying programming logic, so I put in my 'only access to...' restraint. $\endgroup$ – CopyPasteIt Oct 21 '19 at 12:02

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.