# Two numbers sharing an unknown prime factor. Find a method to quickly factor both numbers.

$x$ and $y$ are two number which share a prime factor. You do not know what the prime factor is. Explain how one can factor $x$ and $y$ quickly. Prove it works by using $x = 41685823$ and $y= 39034579$.

I don't really know how to approach this question because sharing a prime factor, does that mean they can share other factors too? Any help would be splendid! Cheers.

Edit: Apparently a classmate said that the two prime are consecutive primes. Maybe this will make the question clearer. Thanks!

• hint: gcd computation – Raymond Manzoni Mar 19 '13 at 23:08
• If $x$ and $y$ share a common divisor, $x-y$ and $x+y$ also share that common divisor and may be easier to factor, at least to remove some of the smaller divisors. – Peter Phipps Mar 20 '13 at 0:08
• LOL,I am a student in UofWaterloo and having Math135 class. I think you are probabily one of my classmates. Anyway, I did not get the right way to solve the quention. But I am sure that it is not as simple as using Euclid's algorithm, as the question required to use RSA and required us to find a way to solve it quickly. Meanwile, the question gives the condition that both N1 and N2 has and only has tow prime factors. – user67593 Mar 20 '13 at 5:27

You can use Euclid's algorithm to find the greatest common divisor, which the prime will divide. If you are given that $x$ and $y$ are semiprimes, that they each have only two prime factors, you can just divide them each by the GCD and have the factorization. The example numbers you have meet this criterion, but I don't see it in the problem statement. If $x$ and $y$ each had four large prime factors and shared two of them, the GCD would be the product of the two shared factors and the rest would be the product of the other two. That is a factorization, but not a complete one.
• Still factoring $\frac{x}{GCD}$, $\frac{y}{GCD}$ and $GCD$ is most of the times much easier than factoring $x,y$... – N. S. Mar 19 '13 at 23:32
• @Michael: whether the primes are consecutive doesn't matter, just how many there are. If they are about the same size, instead of factoring $x$ you are factoring something about $\sqrt x$, so if you are doing trial division you now need to go up to $x^{\frac 14}$ instead of $x^{\frac 12}$. This is the point of N.S.'s comment. – Ross Millikan Mar 19 '13 at 23:56