Modular Arithmetic Inverses/Congruences Questions

2) See the answer here:  https://web2.0calc.com/questions/need-help-fast-please_1

a)

Compute \(10^{-1} \pmod {1001}\). 

Express your answer as a residue from  0 to 1000,inclusive.

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$}.\)

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

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