# 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 Mar 19, 2013 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. Mar 20, 2013 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, 2013 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$... Mar 19, 2013 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. Mar 19, 2013 at 23:56