I have been facing some difficulty solving problems relating the gcd and modulo operator.
If I use the Euclidean algorithm then it works fine when either a or b is small because in one step itself a is reduced to b and b is reduced to a%b.
Here the operator '%' represents modulo operator which gives the remainder r when a is divided by b.
For example:
Euclidean Algorithm: gcd(a, b) = gcd(b, a%b)
gcd(10000000000, 528) = gcd(528, 496)...... (10000000000%528 = 496)
But my problem is that if a is too big and then b is also of the same order then it becomes impossible to write an algorithm in a language like C++ due to integer overflow. Besides why should I bother calculating first a then b and then take the mod of their gcd when I can (if possible) apply some property since I want only the gcd modulo c and not the exact number.
I know I should have asked this on stackoverflow but the properties that I want to know regarding mod and gcd are more related to math.
Long story short, is there a way to find gcd(a, b) % c without having to calculate a or b if a or b are really large expressions. Like a = 100 * 100 * 100 * ...... 10 times or maybe more. Or if I don't know the exact number as they can change and I have to calculate it for different cases.
edit:
Here c is an integer where c < 10000000
a= pow(A, n) + pow(B, n) where A, B, n are all >100000