square ($a \bmod b$)

158 Views Asked by At

suppose $a = np +r$ where $n$ is an integer, $p$ is a prime, $r$ is the remainder. So, $ a \bmod b ≡ r$.

Is $(a \bmod b)^2 = a^2 \bmod b^2$?

I was told this is correct, and can't prove it. (I don't want $a^2 \bmod b$, I am aware they mean different things).

$(a \bmod b)^2 $

$≡ (np +r)^2 $

$= (np)^2 + 2npr + r^2 $

$≡ 2npr + r^2 \bmod p^2 $

$\neq r^2 \bmod p^2 .$

1

There are 1 best solutions below

0
On BEST ANSWER

This is not correct. Take $7=2\cdot 3 + 1$, where $a=7$, $n=2$, $p=3$, and $r=1$. Let $\text{%}$ denote your $\text{mod}$ operation. We have $(7\text{%} 3)^2=1^2=1$, but $7^2\text{%}3^2=49\text{%}9=4\neq 1$.

Of course, this equivalence is possible; take $10=3\cdot 3 + 1$. The equivalence happens when $2nr\equiv 0 \pmod p$. In this case, $2nr=6$, which is indeed divisible by $3$. However, this equivalence does not always hold true, as shown above.