An integer has the properties that and for some integer , what is ?

My solution is as follows:

Let and and , where and . Then

.

Let be a set of relation defined by . We find the integer , and the result is

Remark: The solution involved repeating input of integer until and have a common divisor greater than 2, which doesn't seem very mathematical.

Question:

1. Could anyone show me a better solution?

2. Is it possible to solve this using the Euclidean Algorithm?