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$ ?
Best Answer
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$.