How would I answer the following set of questions related to discrete mathematics?

Question

1) Calculate gcd(2016,208)

I have managed to carry out the following steps:

2016 = 9 x 208 + 144

2016 - 9 x 208 = 144

208 = 144 + 64

208 - 144 = 64

But I am a little stuck on how to proceed after this. And also:

2) Are there any integers a and b such that 2016a + 208b = 1000? If so, what are they? If not, why not?

and

3) Are there any integers a and b such that 2016a + 208b = 1024? If so, what are they? If not, why not?

I believe that to answer question 2 and 3, I will need the gcd from question 1. However, I am not sure how I will use this gcd.

Any help?

Answer 1

$\begin {array}{c|cc}\\ &2016&208\\ 2016&1&0\\ 208&0&1\\ 144&1&-9\\ 64&-1&10\\ 16&3&-29\end{array}$

And $16$ divides $64,$ so we are done.

$16 = \gcd(2016,208)$

$16 =3\cdot 2016 - 29\cdot 208$

In each row the two columns to the right of the $|$ are the coefficients such that $m\cdot 2016 + n\cdot 208$ equals what is in the column on the left.

I look for the largest multiple that I can subtract from the row above, whatever I do on the left, I carry to the right.

b) 16 is not a factor of $1000$ i.e. $\gcd (2016, 1000) = 8$ So, no, it can't be done.

c) $1024 = 2^{10} = 16\cdot 2^6\\ 3\cdot 64 \cdot 2016 - 29\cdot 64 \cdot 208 = 1024$

This is certainly not the only pair that acomplishes the task. But it is an easy pair to find.

Answer 2

just keep going until the residue is $0$:

$144=2\times 64+16$

$64=4\times 16$.

We conclude $gcd(2016,208)=16$.

As for the second question, the answer is no, because $16$ does not divide $1000$.

For the third question the answer is yes. Because $16$ divides $1024$. In order to find the numbers you first find $a$ and $b$ such that $2016a+208b=16$ and then multiply by $1024/16$.

To find that $a$ and $b$ you can use the extended euclidean algorithm.

Answer 3

... 208 - 144 = 64

But I am a little stuck on how to proceed after this.

Just keep going.

$144- 64= 80$

$80 - 64 = 16$

And $64 = 4*16$ so the gcd is $16$.

You don't have to be so careful about doing this. The exact quotients don't matter.

So doing this $\gcd(2016, 208)$. [$208*10 = 2080$]

$= \gcd(2080-2016=64, 208)$. [$4*64=256$]

$= \gcd(64, 256-208=48)$

$=\gcd(64-48=16, 48) $ [$48 = 3*16]$

$=\gcd(16, 3*16) = 16$

You can also use the fact $\gcd(a*k, a*m) = a\gcd(k,m)$ to just get factor out obvious common factors off the bat:

$\gcd (2016 = 4*504, 208= 4*52) = 4*\gcd(504, 52)=4*\gcd(4*126, 4*13)=16*\gcd(126,13)$ and $13$ is prime and $13\not\mid 126$ so $\gcd(126,13) =1$.

So $\gcd(2016, 208) = 16$.

2) Are there any integers a and b such that 2016a + 208b = 1000? If so, what are they? If not, why not?

No. Because all $2016a + 208b = k*\gcd(2016,208)$ for some integer $k$.

So $2016a + 208b = k*16$. But $16 \not \mid 1000$

3) Are there any integers a and b such that 2016a + 208b = 1024? If so, what are they? If not, why not?

Yes. Because the we can find $2016a + 208b = \gcd(2016,208)= 16$.

And $16$ divides $1024$.

What are they? Well...

$2016 = 16*126$ and $208 = 16*13$ and $1024= 16*64$ so we want to find $126a + 13b = 64$.

$126 = 9*13 + 9; 9 = 126- 9*13$

$13 = 9 + 4; 4 = 13- 9$

$9 = 2*4 - 1; 1= 9-2*4$

$1 = (13-4)-2*4 = 13- 3*4$

$= 13- 3(13 - 9) = -2*13 + 3*9$

$=-2*13 + 3(126- 9*13)$

$= 3*126 - 29*13$

So $64 = 126*(3*64) - 13*(29*64)$.

But that's probably not the most convenient of them.