Tricki

## To find a factor of n, find some m such that (m,n) is not 1

### Quick description

If you are trying to design an algorithm for factorizing large numbers, then an easy but useful observation is that if you can find some such that the highest common factor of and is not , then you can find a factor of by applying Euclid's algorithm (which is very efficient) to and .

### Prerequisites

Elementary number theory

### Example 1

Suppose that you didn't know that could be factorized as , and somebody gave you the information that mod . You could reason as follows. If mod , then mod , which is the same as saying that is a factor of . Therefore, cannot be coprime to both and . Applying that to our example, we know that has a factor in common with either or . Applying Euclid's algorithm, we find that and also that .

### General discussion

The simple trick shown here has the obvious drawback that it depended on our being told a highly nontrivial piece of information. But that is not surprising, given that there is no known quick algorithm for factorizing large numbers, and it is widely believed that no such algorithm exists. From a theoretical point of view, the trick is important, and is in fact a vital component of Shor's famous proof that efficient factorizing can be done with a quantum computer.