Practice: Modular Arithmetic

Solution.

Since $24$, $25$, $26$, $47$, and $48$ leave remainders $1$, $2$, $3$, $1$, and $2$, respectively, when we divide them by $23$, we find that: $$ \begin{align*} N&\equiv 24\cdot 25\cdot 26-47\cdot 48\pmod{23}\\ &\equiv 1\cdot 2\cdot 3-1\cdot 2\pmod{23}\\ &\equiv 4\pmod{23}\\ \end{align*} $$

Solution.

We replace big numbers like $15$ by equivalent smaller numbers to help make computing remainders easier. Since $15$ divided by $17$ gives remainder $15$ which is not that small, we instead use the negative number equivalent to $15$ mod $17$, namely $15-17=-2$. Thus: $$ \begin{align*} N&\equiv (15^4)^{10}\equiv ((-2)^4)^{10}\\[0.5em] &\equiv (16)^{10}\equiv (-1)^{10}\equiv 1&&\pmod{17}\\ \end{align*} $$

Solution. Since $4$ divides $100$, any integer that ends in two zeroes are divisible by $4$, so

$$ \begin{align*} 9876543210123456789&= 9876543210123456700+89\\ &\equiv 0+89\\ &\equiv 1&&\pmod{4}\\ \end{align*} $$

Solution. Since $8$ divides $1000$, any integer that ends in three zeroes are divisible by $8$, so

$$ \begin{align*} 12345678987654321&= 12345678987654000+321\\ &\equiv 0+321\\ &\equiv 320+1\\ &\equiv 0+1&&\pmod{8}\\ \end{align*} $$

Solution. Since $8$ divides $1000$, any integer that ends in three zeroes are divisible by $8$, so

$$ \begin{align*} 9876543210123456789&= 9876543210123456000+789\\ &\equiv 0+789\\ &\equiv 789-800\\ &\equiv -11\\ &\equiv -11+16\\ &\equiv 5&&\pmod{8}\\ \end{align*} $$

Solution. Since $25$ divides $100$, any integer that ends in two zeroes are divisible by $25$, so

$$ \begin{align*} 9876543210123456789&= 9876543210123456700+89\\ &\equiv 0+89\\ &\equiv 89-75\\ &\equiv 14&&\pmod{25}\\ \end{align*} $$

Solution. Similar to mod $11$, notice that $10^2=100\equiv -1\pmod{101}$. So if we use blocks of two digits, we have:

$$ \begin{align*} 123456&\equiv 12\cdot 100^2+34\cdot 100+56\\ &\equiv 12\cdot (-1)^2+34\cdot -1+56\\ &\equiv 12-34+56\\ &\equiv 34&&\pmod{101}\\ \end{align*} $$

Solution. We work modulo $F_{16}=15$:

$$ \begin{align*} ABCDE_{16}&\equiv A\cdot 16^4+B\cdot 16^3+C\cdot 16^2+D\cdot 16+E\pmod{15} \end{align*} $$

Since $16\equiv 1\pmod{15}$, we have:

$$ \begin{align*} ABCDE_{16}&\equiv A\cdot 16^4+B\cdot 16^3+C\cdot 16^2+D\cdot 16+E\\ &\equiv A\cdot 1^4+B\cdot 1^3+C\cdot 1^2+D\cdot 1+E\\ &\equiv A+B+C+D+E\\ &\equiv 10+11+(-4)+(-3)+(-2)\\ &\equiv 12\pmod{15} \end{align*} $$

So the remainder of the division is $12$.

Here we used the fact that $C=12\equiv -4\pmod{16}$, $D=13\equiv -3$, and $E=14\equiv -2$ to make hand calculations easier.

Solution. The only values of $n^2\pmod 3$ are $$ 0^2\equiv 0,\quad 2^2\equiv 2,\quad 2^2\equiv 1 \pmod 3 $$ However $$ 14502884\equiv 1+4+5+0+2+8+8+4\equiv 2\pmod{3} $$ so $14502884$ is not a square number.

Solution. We use the first step of the Euclidean algorithm.

$$ 1245567=1\times1234567+11000 $$

So $\gcd(1245567, 1234567)=\gcd(1234567, 11000)$.

We now switch to using prime factorization to find the gcd. Since $11000=2^3\times5^3\times 11$, clearly $2$ and $5$ are not factors of $1234567$. Finally, $$ 1234567\equiv 1-2+3-4+5-6+7\equiv 4\not\equiv 0\pmod{11} $$ so $11$ also does not divide $1234567$. Therefore $\gcd(1234567,1245567)=1$.

Solution. The Euclidean algorithm tells us the following.

$$ \begin{align*} &\gcd(243144287575604577,7843009276212725) \\ =& \gcd(7843009276212725,11000013010102) \\ =& \gcd(11000013010102,9999) \end{align*} $$

We now switch to using prime factorization to find the gcd. Observe that $$9999=9\times1111=3^2\times 11\times 101.$$ We check whether each prime $3$, $11$, and $101$ is a factor of $11000013010102$.

As shown in class, divisibility by $3$ is gotten by working modulo 3 and summing the digits of the number: $$ \begin{align*} &11000013010102\\ \equiv& +1+1+0+0+0+0+1+3+0+1+0+1+0+2\\ \equiv& \,\,10\equiv 1\not\equiv 0\pmod{3} \end{align*} $$

Likewise, we check for divisibility by $11$: $$ \begin{align*} &11000013010102\\ \equiv& -1+1-0+0-0+0-1+3-0+1-0+1-0+2\\ \equiv& \,\, 6\not\equiv 0\pmod{11} \end{align*} $$

We check for divisibility by $101$: $$ \begin{align*} &11000013010102\\ \equiv& +11-00+00-13+01-01+02\\ \equiv& \,\, 0\pmod{101} \end{align*} $$

Only $101$ is a common factor to both numbers, so the gcd is $101$.

Solution. You couldn't. If you bought zero boxes of the 20 nuggets, then $43=6m+9n$ has no integer solutions in $m$ and $n$ since $3$ divides the right side but not the left side: in other words, the equation $43\equiv 6m+9n\pmod{3}$ simplifies to $1\equiv 0\pmod{3}$ which cannot occur.

Likewise if you bought one box of 20 nuggets, then the remaining 23 nuggets must be obtained by buying boxes of 6 and 9 nuggets, but the equation $23=6m+9n$ still has no solution mod 3. Finally you bought two boxes of 20 nuggets, then $43$ is too close to $40$ to be able to get the $3$ extra nuggets by buying the 6 and 9 nuggets.