Any suggestions for a better title would be greatly appreciated.
This is related to a Codeforces problem for modulo arithmetic.
Given an array of non-negative positive integers:
$[a_1, a_2, \dots, a_k]$
If $ a_2, \dots, a_k$ are all some multiples of $a_1$, I have to prove that for every non-negative integer $x$ in the array:
$(((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k = (((x \bmod a_{p_1}) \bmod a_{p_2}) \dots \bmod a_{p_{k - 1}}) \bmod a_{p_k}$
where $a_p$ refers to every permutation of the array.
Example:
n=3 Array: [3, 12, 24]
Result = 0
n=3 Array: [3, 24, 12]
Result = 0
n=3 Array: [12, 3, 24]
Result = 0
n=3 Array: [12, 24, 3]
Result = 0
n=3 Array: [24, 12, 3]
Result = 0
n=3 Array: [24, 3, 12]
Result = 0
n=12 Array: [3, 12, 24]
Result = 0
n=12 Array: [3, 24, 12]
Result = 0
n=12 Array: [12, 3, 24]
Result = 0
n=12 Array: [12, 24, 3]
Result = 0
n=12 Array: [24, 12, 3]
Result = 0
n=12 Array: [24, 3, 12]
Result = 0
n=24 Array: [3, 12, 24]
Result = 0
n=24 Array: [3, 24, 12]
Result = 0
n=24 Array: [12, 3, 24]
Result = 0
n=24 Array: [12, 24, 3]
Result = 0
n=24 Array: [24, 12, 3]
Result = 0
n=24 Array: [24, 3, 12]
Result = 0
What I have tried:
I know that a multiple of one number mod another multiple of the same number will yield either 0 or another multiple. But I simply cannot understand why this can't be the case for non-multiples as well ?
After mod $a_1$, the result is already smaller than all of the elements in the array, so taking further modulos is unnecessary. All we have left to prove is that taking mod $ka$ for $k\in \mathbb{Z}$ will not change the remainder of division by $a$.
Can you prove that?