Let's go through the questions one by one.

QUESTION 2 (20 MARKS)

a) State the Division Algorithm.
The Division Algorithm states that for any two integers $a$ and $b$, with $b > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that:
$a = bq + r \quad \text{where} \quad 0 \leq r < b.$ This algorithm allows us to divide one integer by another to get a quotient and a remainder.

b) Use the Euclidean algorithm to find the gcd(662, 414). Hence or otherwise write gcd(662, 414) in the form 662s + 414t where s and t are integers.

Using the Euclidean algorithm:

1. $662 = 414 \times 1 + 248$
2. $414 = 248 \times 1 + 166$
3. $248 = 166 \times 1 + 82$
4. $166 = 82 \times 2 + 2$
5. $82 = 2 \times 41 + 0$

The gcd is $\text{gcd}(662, 414) = 2$.

Now we write this as a linear combination: From step 4:
$2 = 166 - 2 \times 82$ Substitute $82 = 248 - 1 \times 166$:
$2 = 166 - 2 \times (248 - 1 \times 166) = 3 \times 166 - 2 \times 248$ Substitute $166 = 414 - 1 \times 248$:
$2 = 3 \times (414 - 1 \times 248) - 2 \times 248 = 3 \times 414 - 5 \times 248$ Substitute $248 = 662 - 1 \times 414$:
$2 = 3 \times 414 - 5 \times (662 - 1 \times 414) = 8 \times 414 - 5 \times 662$ Thus, $2 = 8 \times 414 - 5 \times 662$.

So, $s = -5$ and $t = 8$.

c) What are the solutions of the linear congruence $3y \equiv 4 \mod 7$?

To solve $3y \equiv 4 \mod 7$, we need to find the multiplicative inverse of 3 modulo 7.

Using the extended Euclidean algorithm: $7 = 2 \times 3 + 1$ So, $1 = 7 - 2 \times 3$, and the inverse of 3 modulo 7 is $-2 \equiv 5 \mod 7$.

Now multiply both sides of $3y \equiv 4 \mod 7$ by 5: $5 \times 3y \equiv 5 \times 4 \mod 7 \quad \Rightarrow \quad y \equiv 20 \mod 7$ Since $20 \mod 7 = 6$, the solution is $y \equiv 6 \mod 7$.

d) Suppose that a cookie shop has four different kinds of cookies. How many different ways can six cookies be chosen? Assume that only the type of cookie, and not the individual cookies or the order in which they are chosen, matters.

This is a combinations with repetition problem, where the number of ways to choose $r$ cookies from $n$ types is given by the stars and bars formula: $\text{Number of ways} = \binom{r + n - 1}{r} = \binom{6 + 4 - 1}{6} = \binom{9}{3}$ $\binom{9}{3} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84$ So, there are 84 ways to choose six cookies.

Would you like a detailed explanation of any part of these solutions, or should we continue to the next question?

Here are 5 related questions to extend understanding:

1. How does the Euclidean algorithm help find linear combinations for gcd?
2. Can you explain how the stars and bars theorem applies to combinations with repetition?
3. What is the process for finding a modular inverse?
4. How is the Division Algorithm used in practical scenarios beyond gcd calculations?
5. What is the difference between combinations with repetition and without repetition?

Tip: When using the Euclidean algorithm to solve for gcd, make sure to carefully track all steps, as it simplifies finding coefficients for the linear combination (Bezout’s identity).