GCD of random linear combinations
We show that for arbitrary positive integers a(1),..., a(m), with probability 6/pi(2) + o(1), the gcd of two linear combinations of these integers with rather small random integer coefficients coincides with gcd(a(1),..., a(m)). This naturally leads to a probabilistic algorithm for computing the gcd of several integers, with probability 6/pi(2) + o(1), via just one gcd of two numbers with about the same size as the initial data ( namely the above linear combinations). This algorithm can be repeated to achieve any desired confidence level.
gcd linear combinations probabilistic algorithm euler function