Calculating a relative Prime of a number in JAVA?

Question

I am working on a program in which I have calculated a number of type long after applying some calculations according to my algorithm. Now, I have to find a relative prime to this number that I have generated. How can I do this? I know that if two numbers are relative prime then their GCD == 1 but in this case I don't have another number. I have only one number which is getting generated in my program and I need to calculate a relative prime number for this number.

Edit

Condition for generating relative prime is such that:

1 < relative prime < generated Number

Any help is appreciated.

Answer 1

A simple way to get a relative prime:

Now, I have to find a relative prime to this number

For whole number n where n>2 it is always true that n and n-1 are relatively prime. So assuming n isn't 2 or less, simply have n-1 be the output, as it is guaranteed relatively prime. If n equals 2 then your condition is impossible.

Non-trivial relative primes

You can always actually calculate GCDs if you want a non-trivial solution. Use Euclid's method as follows:

long findGCD(long l1, long l2) {
    //end recursion
    if(l2 == 0){
        return number1;
    }
    return findGCD(l2, l1%l2);
}

and use a while loop to try all numbers starting at n+2 until you get a GCD of 1.