0
$\begingroup$

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 ?

$\endgroup$
6
  • $\begingroup$ "But I simply cannot understand why this can't be the case for non-multiples as well ?" Suppose $a$ and $n$ are not both multiples of the same number. Then they are relatively prime. Since there are reltatively prime there exist $k,j$ so that $ak +nj=1$ and $ak \equiv 1 \pmod n$ and $1$ is not a multiple of anything. $\endgroup$
    – fleablood
    Commented May 31, 2020 at 16:13
  • $\begingroup$ @fleablood You have to excuse my ignorance, but what do you mean by $k$ and $j$ ? Is this a particular number theory property that you are referring to ? $\endgroup$
    – ng.newbie
    Commented May 31, 2020 at 16:28
  • $\begingroup$ Bezouts lemma. If $a,n$ are relatively prime there will exist/we will be able to find two integers which we will call $k$ and $j$ so that $ak + nj = 1$ (obviously one of the integers will be negative and the other possitive. So if $ak + nj = 1$ then $ak = 1 - nj$ and so $ak \equiv 1 \pmod n$. $\endgroup$
    – fleablood
    Commented May 31, 2020 at 16:50
  • $\begingroup$ Bezouts lemma can be express as if $\gcd(a,n) =d$ then for any integer $v,w$ then $av + nw = $ some multiple of $d$. And there will exist integers $k,j$ so that $ak + nj = d$. And for any mulitple of $d$, say $dh$ then $a(kh) + n(jh) = dh$ so solutions will exist for all multiple of $d$. So that is why your result holds: If $\gcd(a,n) = d$ not only will all $ak$ but congruent to a multiple of $d$. For any multiple $dm$ there will be a $k$ where $ak \equiv dm \pmod n$. $\endgroup$
    – fleablood
    Commented May 31, 2020 at 16:56
  • $\begingroup$ WHat does: "$(((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}$" mean? What does $b \bmod n = c\bmod m$ mean? $\endgroup$
    – fleablood
    Commented May 31, 2020 at 17:52

1 Answer 1

Reset to default
1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ How can you say that 'After $mod a_1$, the result is already smaller than all of the elements in the array' ? Imagine an array [3,15,24] 24 mod 15 = 9 which is not smaller than all the elements in the array. Could you please elaborate by what you mean ? $\endgroup$
    – ng.newbie
    Commented May 31, 2020 at 15:15
  • 1
    $\begingroup$ $24 \mod 15 = 9$ and then $9\mod 3 = 0$. If you are modding by all $a_i$ you will eventually eventually mod by $a_1$ and as all the results are multiples of $a_1$ then when you mod by $a_1$ you will get $0$. $\endgroup$
    – fleablood
    Commented May 31, 2020 at 18:26
  • $\begingroup$ $15$ is $a_2$. Not $a_1$. YOu haven't modded by $a_1$ yet. So AFTER you mod by $a_1$ you will have a number less than $a_1$ and thus less than all elements in the area. In fact, as all the elements are multiples of $a_1$ you will get $0$ always. $\endgroup$
    – fleablood
    Commented May 31, 2020 at 18:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .