## Common Denominators

June 3, 2009 13:05 by scibuff

In the period of finals ( and studying for finals ) yahoo answers have been flooded with homework and assignment problems 99.9% involve mundane “plug it into a formula” type of solutions. As such, these are of no particular interest to me or for this series. Hopefully, now that most students swapped book for beaches, there will be more interesting questions posted. Meanwhile, here are two short problems I picked some time ago

Problem: Prove that if $p(x)$ is relatively prime to $k(x)$ and $f(x)k(x)\equiv g(x)k(x)\ mod\ p(x)$,then

$f(x)\equiv g(x)\ mod\ p(x)$

Solution: Using $f(x)k(x)\equiv g(x)k(x)\ mod\ p(x)$ it follows

$f(x)k(x) - g(x)k(x) = k(x)\left ( f(x) - g(x) \right ) \equiv 0\ mod\ p(x)$

Since $p(x)$ is relatively prime to $k(x)$ we know that

$k(x)\not \equiv 0\ mod \ p(x)$

and it must be true that

$f(x) - g(x) \equiv 0\ mod\ p(x)$

Thus $f(x)\equiv g(x)\ mod\ p(x)$.

Problem: If $gcd(a,4)=2$ and $gcd(b,4)=2$ prove $gcd(a+b,4)=4$.

Solution: Since $gcd(a,4)=2$ we know that $a = 2p$ for some $p\ \epsilon\ \mathbb{N}$. Similarly, $b = 2q$ for some $q\ \epsilon\ \mathbb{N}$. Notice, that both $p$ and $q$ must be odd. If, lets say, $p$ were even, then $p=2s$ for some $s\ \epsilon\ \mathbb{N}$. But then $a = 2p=2(2s)=4s$ and so $gcd(a,4)=gcd(4s,4)=4$.

Using $a = 2p$ and $b = 2q$ we have $a + b = 2( p + q )$. But since both $p$ and $q$ are odd, their sum is even, i.e.

$p + q = 2t$ for some $t\ \epsilon\ \mathbb{N}$

It now follows that

$a + b = 2( p + q )= 2( 2t ) = 4t$

and so

$gcd(a+b,4)=gcd(4t,4)=4$