Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
    
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

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

share|cite|improve this answer
    
+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$.

share|cite|improve this answer

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}$$

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.