Remainder addition

Question

Here is the problem. We are given two numbers, a and m. We have to print if at some point 'a' will be divisible by 'm' or it will get stuck in a loop.

If a % m is not divisible then new value of a will be a = a + a % m.

My approach to solve the problem was to first check if remainder (a % m) is present in a set. If the remainder is present, we will get stuck in a loop otherwise store remainder (a % m) in a set. Continue until (a % m) is present in the set or until a is divisible by m. My method got accepted but I don't know how it works. The solution is given as for some K check if (a*2^k) is divisible by m. If yes, it will stop else it wont. I tried a little by myself to derive the equation (a*2^k)

a = qm + r; where q is the quotient and r the remainder when divided by m

a = a + a % m

= qm + r + r; since a % m = remainder = r

= qm + 2r

After some point, if loop stops then,

a = q'm + r, where r = 0

So equating, we get

qm + 2r = q'm + 0

(q' - q)m = 2r

(q' - q) = 2r / m

So if 2 * r is divisible by m, we will find that loop will stop(if my derivation is correct). If (a % m) is zero, we will stop. else remainder(r) > 0 then put all values of 1..m - 1 in the above equation and check if (2*r) is divisible by m But we can't simply put all the values of remainder 1...m - 1 in the equation because we can't be sure if all the remainders appear in the sequence. So, how do I derive the above equation(a*2^k)?

Example:

a = 1, m = 5

Ans: It will get stuck in loop

Iter1. a = 1 + 1 % 5 = 2

Iter2. a = 2 + 2 % 5 = 4

Iter3. a = 4 + 4 % 5 = 8

Iter4. a = 8 + 8 % 5 = 11

If we go on, we will find that we will get stuck in a loop. So the answer is no.

a = 3, m = 6

Ans: It will stop.(yes)

a = 3 + 3 mod 6 = 6

a % m = 6 % 6 = 0; hence this will stop.(yes)

Recent problem on codeforces. Only solution was posted without any explanation.

Answer 1

(a + (a % m)) % m = (a + a) % m = (2 * a) % m, so a + (a % m) is divisible by m if and only if a + a is divisible by m and extending this means that you will stop if $2^k a$ is divisible by $m$ for some non-negative integer $k$.

So find the largest odd divisor of $m$ and call it $o$ (easily done by taking the prime factorisation of $m$ and ignoring the powers of $2$). You will stop if and only $o$ divides $a$.

You can find which step you will stop at by comparing the largest power of $2$ which divides $m$ with the largest power of $2$ which divides $a$.