+0

# Modular Arithmetic Inverses/Congruences Questions

0
134
5
+255

a) Compute 10^-1 (mod 1001). Express your answer as a residue from  0 to 1000,inclusive.

2) You have seven bags of gold coins. Each bag has the same number of gold coins. One day, you find a bag of 53 coins. You decide to redistribute the number of coins you have so that all eight bags you hold have the same number of coins. You successfully manage to redistribute all the coins, and you also note that you have more than 200 coins. What is the smallest number of coins you could have had before finding the bag of 53 coins?

Jul 31, 2018

#1
+1

Aug 1, 2018
#2
+21244
+1

a)

Compute $$10^{-1} \pmod {1001}$$

1. Solution

$$\small{ \begin{array}{|rcll|} \hline && 10^{-1} \pmod {1001} \quad | \quad \gcd(10,1001)=1 \\\\ &\equiv & 10^{\phi(1001)-1} \pmod {1001} \quad | \quad \phi(1001)= 1001\cdot(1-\dfrac17)\cdot(1-\dfrac{1}{11})\cdot(1-\dfrac{1}{13})=720 \\\\ &\equiv & 10^{720-1} \pmod{1001} \\ &\equiv & 10^{719} \pmod{1001} \\ &\equiv & 10^{3*239+2} \pmod{1001} \\ &\equiv & 10^{3*239}10^2 \pmod{1001} \\ &\equiv & \left(10^{3}\right)^{239}10^2 \pmod{1001} \quad | \quad 10^3 \equiv -1 \pmod{1001} \\ &\equiv & (-1)^{239}10^2 \pmod{1001} \\ &\equiv & -10^2 \pmod{1001} \\ &\equiv & -100 \pmod{1001} \\ &\equiv & -100+1001 \pmod{1001} \\ & \mathbf{\equiv} & \mathbf{901 \pmod{1001}} \\ \hline \end{array} }$$

2. Solution

$$\begin{array}{rcll} \text{Let} \\ & 10\cdot 10^{-1} \equiv 1 \pmod{1001} \\ \end{array}$$

$$\begin{array}{rcll} \text{Let} \\ & 10\cdot 100 = 1000 \equiv -1 \pmod {1001} \\ \end{array}$$

$$\begin{array}{llcll} \text{square this equation: } \\ & (10\cdot 100)(10\cdot 100) &\equiv& (-1)(-1) \pmod{1001} \\ & (10) (100^2\cdot 10) &\equiv& 1 \pmod{1001} \\ & (10) (100000) &\equiv& 1 \pmod{1001} \quad | \quad 100000 \equiv 901 \pmod{1001} \\ & (10)\underbrace{(901)}_{=(10)^{-1}} &\equiv& 1 \pmod{1001} \\ \end{array}$$

$$\text{So 10^{-1}=\boxed{901} is the multiplicative inverse to 10 modulo 1001}.$$

Aug 1, 2018
#3
+21244
+1

2)
You have seven bags of gold coins.
Each bag has the same number of gold coins.
One day, you find a bag of 53 coins.
You decide to redistribute the number of coins you have so that all eight bags you hold have the same number of coins.
You successfully manage to redistribute all the coins, and you also note that you have more than 200 coins.
What is the smallest number of coins you could have had before finding the bag of 53 coins?

Let n = number of gold coins in every of the seven bags.
Let m = number of gold coins in every of the eight bags.
Let 7n = sum of gold coins in the seven bags.
Let 8m = sum of gold coins in the eight bags.

$$\begin{array}{|rcl|cl|} \hline 7n+53 &=& 8m \\ 7n &=& -53+8m \\\\ 7n &\equiv& -53 \pmod{8} \\ 7n &\equiv& -53+7\cdot 8 \pmod{8} \\ 7n &\equiv& -53+56 \pmod{8} \\ \mathbf{7n} & \mathbf{\equiv} & \mathbf{3 \pmod{8}} \quad | \quad : 7 \\ n & \equiv & 3\cdot 7^{-1} \pmod{8} && 7^{-1} \pmod{8} \quad | \quad \gcd(7,8)=1 \\\\ && &\equiv & 7^{\phi(8)-1}\pmod{8} \quad | \quad \phi(8)= 8\cdot ( 1-\dfrac{1}{2} ) = 4 \\\\ && &\equiv & 7^{4-1} \pmod{8} \\\\ && &\equiv & 7^{3} \pmod{8} \\\\ && &\equiv & 343 \pmod{8} \\\\ && &\equiv & 7 \pmod{8} \\\\ n & \equiv & 3\cdot 7 \pmod{8} \\ n & \equiv & 21 \pmod{8} \\ n & = & 21 +z\cdot 8 \qquad z \in N \\ \hline \end{array}$$

$$\mathbf{n_{min} =\ ?}$$

$$\begin{array}{|rcll|} \hline 7n + 53 &\gt& 200 \\ 7(21 +z\cdot 8) + 53 &\gt& 200 \quad & | \quad -53\\ 7(21 +z\cdot 8) &\gt& 147 \quad & | \quad :7 \\ 21 +z\cdot 8 &\gt& 21 \quad & | \quad -21 \\ z\cdot 8 &\gt& 0 \quad & | \quad :8 \\ \mathbf{z} &\mathbf{\gt}& \mathbf{0} \\ \hline \end{array}$$

$$\text{So z = 1:}$$

$$\begin{array}{|rcll|} \hline n &=& 21 + 1\cdot 8 \\ n &=& 21 + 8 \\ n&=& 29 \\ \mathbf{n} &\mathbf{=}& \mathbf{29} \\ \hline \end{array}$$

The smallest number of coins you could have had before finding the bag of 53 coins is 7*29 = 203

Aug 1, 2018
edited by heureka  Aug 2, 2018
#4
+1

You forgot to multiply by 7 (the question asks for the minimal number of coins you had before you found the eighth bag, not for the minimal number of coins in each of the seven bags.

7*29=203

Guest Aug 1, 2018
#5
+97555
+1

Thanks EP, guest and Heureka,

Here is another take, it is similar to EPs answer only with no trial and error.

It does not use trial and error.

We know that

$$7x+53=8y$$    where x is the number in each original pile and y is the number in the end piles. So obviously x and y are positive integers.

Rearranging I get

$$8y-7x=53$$

One  obvious solution is   $$x=53\;\; and \;\;y=53$$

so I can say

$$8(53 ) - 7(53 ) = 53$$

$$8(53+7t ) - 7(53 +8t) = 53$$     this is true becasue I have simply added 56t and then taken it away again.

so

$$y=53+7t \;\; and\;\; x=53+8t$$

Now you are also told that at the end you have more than 200 coins

so$$8y>200\\ y>25$$

this means that

$$53+7t>25\\ 7t>25-53\\ 7t>-28\\ t>-4\\ \text{So lets try} \;\; t=-3\\~\\ y=53-21=32\\ x=53-24=29$$

8*32-7*29 = 53  excellent

Initially you had $$7x$$ coins.  the smallest number this could have been was $$7*29 = 203$$ coins

Aug 1, 2018