If an integer divides the greadest common divisor of two integers, then it divides any linear combination of the two integers

Let a,b,k be integers. Prove that if k divides a and b, then k divides as + bt for all integers s and t.


Suppose k divides a and b; then there exist integers n and m such that a = kn and b = km. Now we have as + bt = kns + kmt = k(ns + mt) for all s,t, so k divides as + bt.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: