The binary Euclidean Algorithm involves finding the greatest common factor of two numbers by repeatedly dividing by 2 and factoring out powers of 2 until the two numbers are odd. The algorithm is then applied recursively until the two numbers are equal, at which point the gcd is equal to one of the numbers times the power of 2 that was factored out.