Question 1189431: Given that x is a multiple of 15336, what is the greatest common divisor of f(x)=(3x+4)(7x+1)(13x+6)(2x+9) and x
Answer by math_tutor2020(3816)   (Show Source):
You can put this solution on YOUR website!
x is a multiple of 15336
We can say x = 15336k for some integer k.
If we were to expand out
f(x) = (3x+4)(7x+1)(13x+6)(2x+9)
then we'd get something of the form
f(x) = g(x)+4*1*6*9
f(x) = g(x)+216
where g(x) doesn't really matter. The g(x) is the function of all the x terms, x^2 terms, x^3 terms and x^4 term. The coefficients of which aren't of importance.
The string "4*1*6*9" is from multiplying the constants of each factor of f(x).
Since g(x) is composed of all those x terms mentioned, we can write
g(x) = x*h(x)
I factored the common term x out
So,
f(x) = g(x) + 216
f(x) = x*h(x) + 216
This shows that if we were to divide f(x) over x, then we'd get some quotient h(x) and a remainder of 216.
In other words, f(x) = 216 (mod x)
Or we can say f(x) mod x = 216
As you can see, all we care about is the remainder, which is why we can ignore the g(x) and h(x).
Take note how f(x) = x*h(x)+216 is of the form f(x) = qx + r with q = h(x) being the quotient and r = 216 being the remainder.
Next, we have these set of steps
gcd(a,b) = gcd(b,a mod b) ..... see note1 below
gcd(f(x),x) = gcd(x,f(x) mod x)
gcd(f(x),x) = gcd(x,216)
gcd(f(x),x) = gcd(15336k,216)
gcd(f(x),x) = gcd(216*71k,216*1)
gcd(f(x),x) = 216*gcd(71k,1) .... see note2
gcd(f(x),x) = 216*1 .... see note 3
gcd(f(x),x) = 216
Note1: This theorem is very handy for the Euclidean Algorithm
Note2: gcd(ma,kb) = m*gcd(a,b) for any integers a,b,m
Note3: gcd(x,1) = 1 for any integer x
Answer: 216
|
|
|
