# Manual factorization of a large number in hexadecimal format

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?

• 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. Mar 8, 2018 at 12:33
• @quasi 804 F's, followed by a 7, another 300 F's, followed by an E, 803 zeroes followed by a 1. Mar 8, 2018 at 12:36

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.

• Thank you for your response! Mar 8, 2018 at 18:31