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?
$\begingroup$
$\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$– lab bhattacharjeeOct 11, 2015 at 4:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$$
-
$\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$– bazziOct 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$ Oct 11, 2015 at 6:09
-