Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
    
(-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
1  
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
show 2 more comments

4 Answers

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

$$ \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|improve this answer
add comment

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.