Prove it like a Number Theorist!
Find the largest number that will divide 3 9 8 , 4 3 6 , 5 4 2 leaving remainders 7 , 1 1 and 1 5 .
The answer is 17.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Just write the prime factorization of x-p,y-q and z-r. Since we are looking for the greater number that divides all three of them, we want to choose the highest power of each common prime.
The number we want is the product of the highest power of each common prime. This is same as finding their GCD.
Log in to reply
A simpler way would be to note that if x , y , z leave remainders p , q , r when divided by an integer m , then m divides each of x − p , y − q , z − r . By definition of g cd , we have m ∣ g cd ( x − p , y − q , z − r ) from which it directly follows that max ( m ) = g cd ( x − p , y − q , z − r ) since the greatest divisor of any positive integer is that integer itself.
From this, it also follows that if { a i } 1 n and { r i } 1 n be two sequences of integers such that a i ≡ r i ( m o d m ) ∀ 1 ≤ i ≤ n for some integer m , then max ( m ) = g cd ( a 1 − r 1 , a 2 − r 2 , … , a n − r n )
Statement : The largest number that will divide x , y and z leaving remainders p , q and r respectively is equal to gcd ( x − p , y − q , z − r ) .