Hi all,
I'm studying Number Theory on my own. I'm having difficulty proving
the relative primality of t1 and t2 in the following algorithm. Any suggestion or help will be
greatly appreciated.
// An algorithm that returns the sum of two rational numbers.
SUM(r1 /r2 , s1 /s2 )
{
d ← gcd(r2 , s2 );
r3← r2 /d;
s3 ← s2 /d;
T1 ← r1s3 + s1r3 ;
e ← gcd(T1 , d);
t1 ← T1 /e;
t2 ← (r2 /e) · s3 ;
return(t1 /t2 );
}
//gcd stands for greatest common divisor.
Thank you in advance.