mod cancellation: compute $\, n/2\bmod 6\, $ from $\,n \bmod m\,$ for even $n$

Question

I am using the C++ language. I want to calculate these 2 expressions:-

In our case, $x= 100000000000000000$

Expression(1)

$$((3^x-1)/2)\mod7$$

The numerator $3^x-1$ is always divisible by $2$(basic number theory)

I calculated the above expression using Extended-Euclid-Gcd algorithm. The above algorithm only works when gcd(denominator,mod-value)=1...in our case $\gcd(2,7)=1$ . So we were able to calculate it using the above algorithm.

Expression(2)

$$((3^x-1)/2)\mod6$$

The numerator $3^x-1$ is always divisible by $2$(basic number theory-again)

Now, how do I calculate the above expression as $\gcd(2,6)=2$ which is not equal to $1$ ?

Answer 1

Set $$y = \frac{3^x - 1}{2}.$$

Let $0 \leq b < 6$ such that $y = 6a + b$ for some integer $a$. Then $$2y = 12a + 2b$$ and $0 \leq 2b < 12$, so you could simply compute $3^x - 1 \mod{12}$.

Answer 2

For your first case, the extended Euclidean algorithm is probably the best way in general, as long as the denominator and modulus are coprime.

For your second case, consider $4\div 2$ modulo $6$. What should that be? Should it be $2$, as $2\cdot 2\equiv 4$? Or should it perhaps be $5$, as $5\cdot2\equiv 4$? There just isn't a single answer, and thus you can't really divide by $2$ modulo $6$.

If you're interested in what $\frac k2$ corresponds to modulo $6$, you have to find $k$ modulo $2\cdot 6=12$ and work your way from there. For instance, if $k\equiv_{12}4$, then $\frac k2$ is either $2$ or $8$ modulo $12$, meaning it must be $2$ modulo $6$.

Answer 3

Dividing by $\boldsymbol{q}$ when the modulus is divisible by $\boldsymbol{q}$

Note that $$ aq\equiv bq\pmod{pq} $$ precisely when $$ a\equiv b\pmod{p} $$ Thus, for $n\gt0$, $$ 3^n-1\equiv\left\{\begin{array}{}2&\text{if $n$ is odd}\\8&\text{if $n$ is even}\end{array}\right.\pmod{12} $$ implies $$ \frac{3^n-1}2\equiv\left\{\begin{array}{}1&\text{if $n$ is odd}\\4&\text{if $n$ is even}\end{array}\right.\pmod{6} $$

---

A More Detailed Answer

This can be solved mod $6$ by solving mod $3$ and mod $2$, then applying the Chinese Remainder Theorem.

For $n\gt0$, $3^n\equiv0\pmod3$; therefore, $$ \frac{3^n-1}2\equiv1\pmod3 $$ To compute $$ \frac{3^n-1}2\pmod2 $$ we can to look at $$ 3^n-1\equiv(-1)^n-1\pmod4 $$ to get $$ \frac{3^n-1}2\equiv\frac{(-1)^n-1}2\equiv\left\{\begin{array}{}0&\text{if $n$ is even}\\1&\text{if $n$ is odd}\end{array}\right.\pmod2 $$ Then the Chinese Remainder Theorem says we can combine the results mod $3$ and mod $2$ to get $$ \frac{3^n-1}2\equiv\left\{\begin{array}{}4&\text{if $n$ is even}\\1&\text{if $n$ is odd}\end{array}\right.\pmod6 $$

Answer 4

For even $\,n,\,$ if we wish to compute $\ n/2\bmod 6\ $ then we need to know $\,n\bmod 12,\,$ i.e. we need to double the modulus to balance the division by $\,2,\,$ namely

$$\begin{align} {\rm notice}\ \ \ \, \color{}{n/2 \equiv r\!\!\!\pmod{\!6}}&\!\iff n\equiv 2r\!\!\!\!\pmod{\!12}\\[.4em] {\rm because}\ \ \ n/2\ =\ r\ +\ 6\,k\ \ &\!\iff n = 2r\ +\ 12\,k\end{align}\qquad$$

So first we compute $\,n\bmod 12 = 2r,\, $ then $\ r = n/2 \bmod 6\ $ by above, i.e.

$$\begin{align} r\,=\, \color{#c00}{n/2\bmod 6} \,&=\ \color{#c00}{(n\bmod 12)/2}\\[.4em] {\rm e.g.}\ \ \ 18/2 \bmod 6\, &= (18 \bmod 12)/2 = 6/2 = 3\end{align}\qquad$$

Beware $ $ We get the wrong result $\,0\,$ if we use $18\bmod 6$ vs. $18\bmod 12.\,$ See here for more.

Remark $ $ Below is a simpler way to compute $\,3^x\bmod 12\ $ (vs. using CRT mod $3\ \& 4)$

$$ 3^{K+{\large 1}}\!\bmod 12 = 3(3^K\!\bmod 4) = 3((-1)^K\!\bmod 4) = 3\ \ {\rm if}\ \ 2\mid K, \ {\rm else}\, \ 9$$

where we used $\ ab\bmod ac = a(b\bmod c) = $ mod Distributive Law

Note that our formula above is a special case of this law, namely

$$ 2\mid n\,\Rightarrow\ \color{#c00}{n\bmod 12\, =\, 2(n/2\bmod 6)}\qquad\qquad\qquad $$