Tuesday, March 14, 2017

how does remainder vary with multiples of a given number




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 xr(modg) and from this you wish to know the value of x(modfg)? There is not enough information yet, but if you had a few more pieces of information, namely the value of x(modf) 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(mod10)=5, i.e. the last digit of x is 5. We want to know what x(mod1010) 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(mod2)=1, i.e. that x is odd. We want to know what x(mod25) 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 xs(modf), then we would simultaneously know x1(mod2) and x2(mod5), which by chinese remainder theorem would imply that x7(mod10)






If your question was instead about finding the value of (xf)(modg) given the information that xr(modg), then this is simply a matter of arithmetic. You would have xfrf(modg).



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...