# Modular arithmetic problem

It is given that $911$ is a prime number. Integers $x$ and $y$ are chosen such that $9x+11y$ is a multiple of $911$. For what positive integer value $N<1000$ will $11x+Ny$ definitely be a multiple of $911$?

Someone please give the solution for it with explanation.

-
Are you familiar with congruences? –  Berci Mar 20 '13 at 20:26
yes, I a=b (mod c). –  Raushan Kumar Mar 20 '13 at 20:38
Perfect. $\,\,\!\!$ –  Berci Mar 20 '13 at 20:55
(-1) for "Someone please give the solution". The road to the answer is what matters, not the answer itself. And use the homework-tag if this is homework. –  TMM Mar 20 '13 at 21:46
So there seems to be two ways of interpreting what was said. Everyone should vote as they see fit, but I just felt I should mention that "give the solution ... with explanation" sounded different to me. –  robjohn Mar 21 '13 at 21:53

Hint $\rm\ mod\ 911\!:\, 9x\!+\!11y\equiv 0 \Rightarrow x \equiv -11y/9\Rightarrow 11x\equiv -11^2 y/9 \equiv (2\cdot 911\! -\!121)\,y/9\equiv \color{blue}{189}y$

Remark $\$ Replying to a comment, I don't compute $\rm\,1/9\,\ mod\,\ 911.\:$ Instead I use that $\rm\:mod\ 911\!:\, -11^2/9\,\equiv\, (911\,n\!-\!11^2)/9,\:$ so I compute $\rm\:n\:$ such that $\rm\:9\mid 911\,n-11^2,\$ i.e. $\rm\: mod\ 9\!:\ 0\,\equiv\, 911\,n\!-\!11^2\!\equiv\, \color{#C00}2n\!-\!\color{#0A0}4\,$ $\Rightarrow$ $\,\rm n\equiv 2,\:$ so $\rm\: \frac{-11^2}9 \equiv \frac{911(2) - 11^2}9$ $\equiv 100(2)\!-\!11 \equiv \color{blue}{189}.\:$
(Note that casting nines allows one to quickly do the above calculation purely mentally, since $\rm\: mod\ 9\!:\ 911\equiv 9\!+\!1\!+\!1\equiv \color{#C00}2,\:$ and $\rm\:11^2\!\equiv (1\!+\!1)^2\!\equiv \color{#0A0}4).$

-
+1 Made it much easier... Anyway, this $/9$ here means $\cdot 405$ [modulo $911$], as $405$ is the multiplicative inverse of $9$ as I calculated. –  Berci Mar 20 '13 at 20:53
@Berci Thanks. But I don't need to need to calculate $\rm\ 1/9\ mod\ 911.\:$ Instead, the arithmetic is all very simply single-digit calculations that can be quickly mentally performed, as I explain in the remark added in an edit. –  Math Gems Mar 20 '13 at 21:33

Introducing the notation $a\equiv b \pmod{911}$ for $911\,|\, b-a$, we have $$9x+11y\equiv 0 \pmod{911}$$ That is, $9x\equiv -11y$. Now, the multiplicative inverse of $3$ modulo $911$ can be easily found, as $3\cdot 304=912\equiv 1\pmod{911}$. It follows, that $304^2=92416$ is multiplicative inverse of $3^2$ modulo $911$, which is congruent to $$304^2=92416=911\cdot100 + 911 + 405 \equiv 405 \pmod{911}$$ So, we have that $405\cdot 9\equiv 1 \pmod{911}$, so $$x+405\cdot 11y\equiv 405\cdot(9x+11y)\equiv 0 \pmod{911}$$ Further, $11\cdot 405=4455\equiv 811 \equiv -100 \pmod{911}$, so we have $x-100y\equiv 0$, now multiplying by $11$ we will soon get an $N$: $$11x-1100y\equiv 0 \pmod{911}$$ And finally, calculate the remainder of $1100$ mod $911$, that is $189$, so $911-189=722$ will be good for $N$.

-

Hint $\$ Below is a very simple alternative approach suggested by the form of the numbers:

$$\begin{eqnarray}\rm mod\ \ 911\!: &&\rm\ \ {-}11\,x&\equiv&\rm\, N\,y \\ &&\rm -900\,x\,&\equiv&\,\rm 1100\,y\\ \rm adding\ \Rightarrow &&\rm -911\,x &\equiv&\rm (N+1100)\,y \\ \Rightarrow && \qquad \ 0 &\equiv&\rm\ \, N + 189 \end{eqnarray}$$

-

\begin{align} 9x+11y&\equiv0\pmod{911}\tag{1}\\ 11x+ny&\equiv0\pmod{911}\tag{2} \end{align} $11\times(1)-9\times(2)$ is $$(121-9n)y\equiv0\pmod{911}\tag{3}$$ Since we don't necessarily have $y\equiv0\pmod{911}$, we must have $$9n\equiv121\pmod{911}\tag{4}$$ which, using an algorithm similar to the Euclid-Wallis Algorithm yields $$n\equiv722\pmod{911}\tag{5}$$

-