Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 \begin{equation} 2\cdot3\cdot5 + 2^3 = 2(3 \cdot 5 + 2^4) = 2\cdot19 = N_3 \end{equation} 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 ...

share|cite|improve this answer
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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.