1
$\begingroup$

I have a large hexadecimal number that I'd like to factorize in two prime numbers. I am sure that this number can be built with two primes. It can't be done with the computer because it's a very large number, but I think there's a logical way to solve this problem because the hex number is a bunch of F's followed by zeroes with a 1 at the end (FFF...000...1). It also has one 7 and one E, but I guess that once I know how to tackle FFF...000...1, I could easily solve the same problem if the number has a 7 and an E. Any idea how to start with this problem?

$\endgroup$
2
  • 1
    $\begingroup$ Please give the actual form, including the location of the $7$ and the $E$, as well as the exact number of $F$'s and $0$'s. $\endgroup$
    – quasi
    Mar 8, 2018 at 12:33
  • $\begingroup$ @quasi 804 F's, followed by a 7, another 300 F's, followed by an E, 803 zeroes followed by a 1. $\endgroup$
    – pvdsp
    Mar 8, 2018 at 12:36

1 Answer 1

4
$\begingroup$

Let $n$ be the specified number.

Here's the plan . . .

  • Break up $n$ as a sum of the specified parts.$\\[4pt]$
  • Express each part as compactly as possible, first in terms of powers of $16$, and then in terms of powers of $2$.$\\[4pt]$
  • Combine terms where possible.$\\[4pt]$
  • Hope that the resulting expression factors algebraically.$\\[4pt]$

Tedious, but straightforward.

Let's try it . . .

$804\;$hex$\;\text{F}$'s, followed by $1106$ hex $0$'s, is equal to $$(16^{804}-1)(16^{1106})=16^{1910}-16^{1106}=2^{7640}-2^{4424}$$ One hex $7$, followed by $1105$ hex $0$'s, is equal to $$(7)(16^{1105})=(8)(16^{1105})-16^{1105}=2^{4423}-2^{4420}$$ $300\;$hex$\;\text{F}$'s, followed by $805$ hex $0$'s, is equal to $$(16^{300}-1)(16^{805})=16^{1105}-16^{805}=2^{4420}-2^{3220}$$ One hex $\text{E}$, followed by $804$ hex $0$'s is equal to $$(14)(16^{804})=(16)(16^{804})-(2)(16^{804})=2^{3220}-2^{3217}$$ hence we have \begin{align*} n&= \left(2^{7640}-2^{4424}\right) + \left(2^{4423}-2^{4420}\right) + \left(2^{4420}-2^{3220}\right) + \left(2^{3220}-2^{3217}\right) + 1 \\[4pt] &=2^{7640} - \left(2^{4424}-2^{4423}\right)-2^{3217}+1\\[4pt] &=2^{7640} - 2^{4423} - 2^{3217} + 1\\[4pt] &=(2^{4423}-1)(2^{3217} - 1)\\[4pt] \end{align*} Maple says that $2^{4423}-1$ and $2^{3217}-1$ are both prime.

$\endgroup$
1
  • $\begingroup$ Thank you for your response! $\endgroup$
    – pvdsp
    Mar 8, 2018 at 18:31

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.