## 187 – Quiz 8

Here is quiz 8.

Problem 1 asks to find integers $x,y$ such that $13 x+8y=1.$

One way of doing this is to follow the Euclidean algorithm to compute the g.c.d. of 13 and 8: ${\mathbf 13}={\mathbf 8}\times1+{\mathbf 5},$ ${\mathbf 8}={\mathbf 5}\times1+{\mathbf 3},$ ${\mathbf 5}={\mathbf 3}\times1+{\mathbf 2},$ ${\mathbf 3}={\mathbf 2}\times1+{\mathbf 1}.$

Now we work from these equations, starting with the last one and going up, expressing the remainders as linear combinations of the other two numbers: $1=3-2.$

Since $2=5-3,$ we have $1=3-(5-3)=3\times2-5.$

Since $3=8-5,$ we have $1=(8-5)\times2-5=8\times 2-5\times3.$

Since $5=13-8,$ we have $1=8\times 2-(13-8)\times3=8\times 5-13\times3.$

We have found that $x=-3,$ $y=5$ satisfy $13x+8y=1.$

There are, of course, other ways we could have found these numbers, including trial and error: Simply list the multiples of 13 in order: 13, 26, 39, …, and note that 39 is 1 shy of a multiple of 8: $13\times 3=8\times 5-1,$ giving the same solution as before.

Problem 2 asks for integers $x,y,$ neither of which is 0, and such that $13x+8y=0.$

Perhaps the easiest solution is to make $x=8,$ $y=-13.$

Problem 3 asks for integers $x,y$ different from those in problem 1, such that $13x+8y=1.$

One way of finding these numbers is by adding the solutions to problems 1 and 2: $13\times(-3)+8\times 5=1,$ $13\times8+8\times(-13)=0,$

so $13\times 5+8\times(-8)=1.$

We could have also subtracted the solution to problem 2 from the solution to problem 1, to obtain $13\times(-11)+8\times18=1.$

Or we could have squared the solution to problem 1: $(13\times(-3)+8\times 5)^2=1^2=1,$ or $13^2\times 9+2\times13\times(-3)\times8\times5+8^2\times25=1,$ or $13\times(13\times9+2\times-3\times8\times5)+8\times(8\times25)=1.$

Problem 4 asks  for the number of injective functions from $A=\{a,b,c,d\}$ into $B=\{1,2,3,4,5\}.$

Let $f:A\to B$ be 1-1. There are 5 possibilities for the value $f(a).$ Whatever it is, $f(b)$ can take any value in $B$ other than $f(a),$ so there are 4 possibilities for $f(b).$ The value $f(c)$ can be anything in $B$ other than $f(a)$ or $f(b),$ so there are 3 possibilities for $f(c).$ Finally, $f(d)$ can take any of the remaining 2 values. This gives a total of $5\times4\times 3\times 2=120$ injective functions.

Note that this is the same as the number of lists of length 4 without repetitions with values taken from the set $B.$