Knowing the remainder of an unknown number for a given number, is it possible to calculate the remainder of the unknown number for a (known) multiple of the given number. i.e. For r, g and f known, x unknown in following
r = x mod g
R = x mod (fg)
find R.
Answer
Reworded in terms of modular arithmetic, you say you know that $x\equiv r\pmod{g}$ and from this you wish to know the value of $x\pmod{f\cdot g}$? There is not enough information yet, but if you had a few more pieces of information, namely the value of $x\pmod{f}$ as well as knowing that $\gcd(f,g)=1$, you could then use the chinese remainder theorem to get your final answer.
An example of why we don't have enough information without these:
Consider $g=10, f=10, r=5$. We are told that $x\pmod{10}=5$, i.e. the last digit of $x$ is $5$. We want to know what $x\pmod{10\cdot 10}$ is, i.e. we want to know the last two digits of $x$. If all we know is the last digit of $x$, we have no way of knowing what the second to last digit of $x$ is. For example, both $15$ and $25$ have their last digit equal to $5$ but they have different second to last digits.
Similarly, if $g=2, f=5, r=1$. We are told that $x\pmod{2}=1$, i.e. that $x$ is odd. We want to know what $x\pmod{2\cdot 5}$ is, i.e. we want to know the last digit of $x$. If all we know is that $x$ is odd, we cannot determine uniquely which of the digits $1,3,5,7,9$ is the last digit of $x$.
If we knew however that $g=2,f=5,r=1$ and that $s=2$ where $x\equiv s\pmod{f}$, then we would simultaneously know $x\equiv 1\pmod{2}$ and $x\equiv 2\pmod{5}$, which by chinese remainder theorem would imply that $x\equiv 7\pmod{10}$
If your question was instead about finding the value of $(x\cdot f)\pmod{g}$ given the information that $x\equiv r\pmod{g}$, then this is simply a matter of arithmetic. You would have $x\cdot f\equiv r\cdot f\pmod{g}$.
No comments:
Post a Comment