# Finding the sum of two numbers knowing only the primes

Pretend $N_1$ is the prime factorization of 30 and $N_2$ is the prime factorization of 8. Is there a way, using only $N_1$ and $N_2$, to get the prime factorization of the sum, 38?

It is easy to do product (just merge the prime factors) but I do not know about addition.

-
What ever algorithm you make will probably be more complicated than just factoring the sum. Guessing that's not the point though? – jameselmore Jul 18 '13 at 23:39
@jameselmore right; I am working with some large numbers in a program and I can't store the full value, so I am trying to store the prime factorization instead to save memory. – MyNameIsKhan Jul 18 '13 at 23:40
I don't know if it works in a general setting but in this case $N_1 = 2\cdot3\cdot5$ and $N_2 = 2^3$ so $$2\cdot3\cdot5 + 2^3 = 2(3 \cdot 5 + 2^4) = 2\cdot19 = N_3$$ and 19 happens to be prime, so $N_3$ is the prime factorization of 38. – Alex Jul 18 '13 at 23:42
How big are the numbers you mean? Many languages have packages available that handle arbitrary size integers, freeing you from a $2^{64}$ limit. Storing factorizations means you cannot represent many of the numbers-any with prime factors too large to store. – Ross Millikan Jul 18 '13 at 23:43
@RossMillikan I am doing this in C++ for something work-related and I can't use bignums for this – MyNameIsKhan Jul 18 '13 at 23:44

You can make it a little easier by looking for common factors. In your example, $2$ is an element of both factorizations, so will be a factor of the sum. If there are lots of common factors, that will help a lot. Otherwise, not so much ...

-
are there some general results ( assuming for example that $y$ and $x$ have no common divisors) that connect the prime factorisation of $(x+y)$ to that of $x$ and $y$? – sigmatau Jul 18 '13 at 23:51
@AmireBendjeddou: Not that I am aware of. Addition and factoring don't play nicely together. – Ross Millikan Jul 19 '13 at 0:03
Take $47$ and $53$. Their sum is $100$, yet both are prime. You need more than just a prime factorization to factor a sum - you need to know the remainders modulo all the primes and prime powers less than the two numbers also and look for cases where the sums of the two numbers modulo those primes - and prime powers potentially - cancel out. – Foo Barrigno Sep 24 '13 at 11:43

What you want is pretty much hopeless. If $N_1$ and $N_2$ both have easy but disjoint factorisations (many small factors but not the same ones in $N_1$ and $N_2$), then $N_3$ is quite likely to involve by contrast some very large prime factor(s). The ABC-conjecture makes a precise (but not so easy to formulate) statement to this effect. It hasn't been proved, but then it hasn't been disproved either.

-

This might get you closer:

$$\frac{1}{30}+\frac{1}{8}=\frac{(30 + 8)}{gcd(30 +8,lcm(30,8))}=\frac{19}{lcm(30,8)}=\frac{19}{120}$$

where $gcd(\cdot,\cdot)$ is greatest common denominator and $lcm(\cdot,\cdot)$ is the lowest common multiple

-