"Nathan claims that if you pick a two-digit number whose units digit is odd, but not 5, such as 37, and multiply it by some positive integer n and tell him the last two digits of your result that he can tell you the remainder when n is divided by 25. Is Nathan's claim possible? Why or why not?"

So, the units digit is odd and not $5$. That means $100$ and our number is coprime. I know that $100 = 2^25^2$, but from here I don't know what other conclusions I can make.


  • 1
    $\begingroup$ If you tell him 66, how is he suppose to know if n is 6 and your original number is 11) or 2 (and your number is 33)? $\endgroup$ – T.J. Gaffney Dec 23 '13 at 21:16
  • 2
    $\begingroup$ Does Nathan know the two digit number which is relatively prime to $10$? $\endgroup$ – robjohn Dec 23 '13 at 21:26
  • $\begingroup$ Nathan can claim that $n$ is some particular number, but $3$ and $1$ are equivalent modulo $10$ under multiplication by $\{4, 2\}$. What mechanism could Nathan use to separate these results? $\endgroup$ – abiessu Dec 23 '13 at 21:48

Nathan's claim can be stated as follows: let $x$ be a number that is coprime to $100$, then given the equation $$ nx \equiv c \pmod{100} $$ Where $x$ and $c$ are known, we may determine the value of $n$ modulo $25$.

Hint: Chinese remainder theorem

  • $\begingroup$ Sorry, but what would $c$ be since you said that $x$ and $c$ are known? So $n$ is the integer we are multiplying by, $x$ is the two digit integer that is coprime with $100$, and $c$ is then the remainder of $nx$ modulo $100$? $\endgroup$ – asd Dec 23 '13 at 21:24
  • 1
    $\begingroup$ I'm thinking of the problem from Nathan's perspective. $n$ is the secret number we're multiplying by $x$, which is coprime to $100$. $c$ is "the last two digits" of the product. $\endgroup$ – Omnomnomnom Dec 23 '13 at 21:34
  • $\begingroup$ How do we know that $c$ is the last two digits of the product? $\endgroup$ – asd Dec 23 '13 at 22:14
  • $\begingroup$ Or rather, why are we able to create this equation $\endgroup$ – asd Dec 23 '13 at 22:21
  • $\begingroup$ Again, I'm thinking about the problem from nathan's perspective. I know the number (coprime to $100$) that was multiplied by $n$, and I've called this $x$. The other person has multiplied $x$ by his mystery number $n$ and told me the last two digits, and I'm calling this number (that I've been given) "$c$". The equation simply states that if you multiply $n$ by $x$ and extract the last two digits, you get $c$. Does that make sense? $\endgroup$ – Omnomnomnom Dec 24 '13 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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