1
$\begingroup$

Knowing $$(a \mod p)\ \text{and}\ (a \mod 2)$$ can we definitely say what is $$\left\lfloor \frac{a}{2}\right\rfloor \mod p$$ where $p$ is a prime. If not possible what else is required to do the same?

$\endgroup$
1
  • 1
    $\begingroup$ If $a\equiv1\pmod2, a=2m+1, a\equiv2m+1\pmod p$ $\left\lfloor\dfrac a2\right\rfloor\equiv m\pmod p$ If $a\equiv0\pmod2, a=2m, a\equiv2m\pmod p$ $\left\lfloor\dfrac a2\right\rfloor\equiv m\pmod p$ $\endgroup$ Oct 11, 2015 at 4:48

1 Answer 1

1
$\begingroup$

By knowing $a\!\!\mod p$ and $a\!\!\mod 2$, we know $a\!\!\mod 2p$ by Chinese Remainder Theorem.

As such, let $a=2pq+r$, where $q$ and $r$ are the quotient and remainder.

$$\left\lfloor\frac{a}{2}\right\rfloor=\left\lfloor\frac{2pq+r}{2}\right\rfloor\\=\left\lfloor\frac{2pq+r}{2}\right\rfloor\\=pq+\left\lfloor\frac{r}{2}\right\rfloor\equiv\left\lfloor\frac{r}{2}\right\rfloor\mod p$$

$\endgroup$
3
  • $\begingroup$ Actually I don't know the exact value of a. I only know $$a\ mod\ x$$ where x is any positive integer. Now how to approach this ? $\endgroup$
    – bazzi
    Oct 11, 2015 at 5:38
  • $\begingroup$ The intermediate steps use $q$, although you only know $r$. The aim of these steps is to show that $q$ does not matter. $\endgroup$
    – Element118
    Oct 11, 2015 at 6:09
  • $\begingroup$ Got it.Thanks for your time. $\endgroup$
    – bazzi
    Oct 11, 2015 at 8:19

You must log in to answer this question.

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