# Modular Arithmetic [Confusion]

"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.

Help?

• 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)? – T.J. Gaffney Dec 23 '13 at 21:16
• Does Nathan know the two digit number which is relatively prime to $10$? – robjohn Dec 23 '13 at 21:26
• 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? – 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$.
• 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$? – asd Dec 23 '13 at 21:24
• 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. – Omnomnomnom Dec 23 '13 at 21:34
• How do we know that $c$ is the last two digits of the product? – asd Dec 23 '13 at 22:14
• 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? – Omnomnomnom Dec 24 '13 at 23:55