mod cancellation: compute $\, n/2\bmod 6\, $ from $\,n \bmod m\,$ for even $n$ 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$  ?

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
$$
