1
$\begingroup$

How to prove/disprove that (a mod p) mod q = (a mod q)mod p ?

Supposing $p < q$, we have 3 situations:

  1. $a{\space}{\epsilon}{\space}[0, p)$, obviously the statement is true for this case

  2. $a{\space}{\epsilon}{\space}[p, q)$

$a{\space}mod{\space}p{\space}mod{\space}q=(a-a/p)mod{\space}q=a{\space}mod{\space}q-a/p{\space}mod{\space}mod{\space}q=a-a/p$

and

$a{\space}mod{\space}q{\space}mod{\space}p=a{\space}mod{\space}p=a-a/p$

  1. and $a > q$ which reduces to first two situations.

Taking these three situation I have found that the statement is true. I am missing something ?

$\endgroup$
2
$\begingroup$

Your solution is pretty sloppy, and as usual, sloppiness leads to wrong results.

  1. Yes, if $a<p$, the equality holds, but it isn't enough to just say "obviously."
  2. Your solution for $p\leq a < q$ makes no sense. I have no idea what you were trying to prove.
  3. How exactly does $a>q$ reduce to the first two situations? You can't just say it does without proving it.

Also:

Try the values of $a=10, p=10, q=3$.

$\endgroup$
  • 3
    $\begingroup$ A number theorist somewhere dies when people write things like let $p=10$. :) $\endgroup$ – Ravi Mar 31 '16 at 7:35
  • $\begingroup$ @Jake Well OP didn't specify if $p$ is prime. But even so, $a=p=3$ works just as well if $q=2$. $\endgroup$ – 5xum Mar 31 '16 at 7:37
  • 1
    $\begingroup$ I know, I know. I was just making a joke. :) +1 $\endgroup$ – Ravi Mar 31 '16 at 7:37
  • 2
    $\begingroup$ @Jake I thought so. In fact, I was sure with a $p$ value of $<0.05$ :). $\endgroup$ – 5xum Mar 31 '16 at 7:38
  • 1
    $\begingroup$ Oh wow. That just took it to a whole new level. $\endgroup$ – Ravi Mar 31 '16 at 7:44
2
$\begingroup$

There is no need to go very far:

$$3\bmod 2\bmod 3=1,\\3\bmod3\bmod2=0.$$

$\endgroup$
1
$\begingroup$

I do not think talking about an element modulo $p$ and then modulo $q$ makes much sense because when we talk about $3\pmod 7$ we are simultaneously talking about all integers that leave a remainder of $3$ when divided by $7$. This includes numbers like $3,10,17$ etc.

So if you want to talk about $3 \pmod 7 \pmod 2$, should this be $1$ because $3$ is $1\pmod 2$ or should this be $0$ because $10$ is $0\pmod 2$? It's pure chaos.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.