How Gcd works in this code?

Question

I tried solving a question on hackerearth and i was not able to solve it so i saw editorial.They gave only code without explanation.Can u expain logic behind why gcd used here?

Question:

Scooby and all of his friends have gathered for a party. There are N friends present. Scooby is really happy to see all of his friends in one place and is excited to greet them.

All N friends are seated in a circle, and are numbered from 0 to N-1. Scooby is initially sitting beside the Ath friend. After greeting one friend, he goes clockwise to the Bth next friend, sits next to him and greets him. He repeats this till he returns to the Ath friend.

In his excitement, it is possible that Scooby misses out on greeting some friends. Your job is to find the number of friends (including A) that Scooby will have greeted before reaching back to A.

Solution given:

int main()
{
int T;
cin>>T;
while(T--)
{
    long long N,A,B;
    cin>>A>>B>>N;
    long long g=gcd(B,N);
    cout<<N/g<<endl;     
    }
return 0;
}

Answer 1

To explain the solution of the above problem I will first show that the answer is - LCM(B,N)/B and then show you how this is equal to N/GCD(B,N).

First Part-
Now assume that when it again reaches A after following the above mentioned steps he would have greeted f friends.(Note no two friends greeted through the above mentioned procedure can be same). Moreover, assume that when he reached A he would have made r rounds of the circle.
Now we can say that - f * B = r * N = C.
Let this be equal to some constant C. Clearly C is some multiple of B and N moreover, it is the Lowest Common Multiple(LCM) of B and N(as we want to give answer as soon as it reaches for the first time).
So f = LCM(B,N)/B. Note f is the number of friends he greeted so it is the required answer.

Second Part-
For two positive integers a and b with their GCD and LCM g and l respectively, we have the following relation - a*b = g*l.
From the above relation we can say that -
LCM(B,N)*GCD(B,N) = B*N
=> LCM(B,N)/B = N/GCD(B,N)

So finally we have our answer = LCM(B,N)/B = N/GCD(B,N).