How to evaluate below expression of modular arithmetic?

Question

How to evaluate (10^18)%(10^9 + 7) using modular arithmetic? How to proceed and what will be the steps?

Answer 1

(10^9 + 7) * (10^9 - k) = 10^18 + 7*10^9 - k*10^9 - 7k
k=7: (10^9 + 7) * (10^9 - 7) = 10^18 - 49
10^18 = (10^9 + 7) * (10^9 - 7) + 49
10^18 % (10^9 + 7) = 49

Thought process:

The form of this problem is a^2 % (a+k).
Recall (a+k)*(a-k) = a^2 - k^2
So a^2 % (a+k) = k^2 % (a+k)
Now because k is so small, k^2 % (a+k) = k^2.

Answer 2

Using modular arithmetic,

$10^9\equiv-7\pmod{10^9+7}$,

so $10^{18}=(10^9)^2\equiv(-7)^2=49\pmod{10^9+7}$.

Answer 3

Building on dave's answer above but in a way that I can understand -

Given

10^18 = (10^9 + 7) * (10^9 - 7) + 49
10^18 % (10^9 + 7) = 49
....
Generalising ...
===> a^2 = (a + b) * (a - b) + b^2
===> a^2 % (a + b) = { (a + b) * (a - b) + b^2 } % (a + b)
Consider : { (a + b) * (a - b) + b^2 } % (a + b)
===> [ { (a + b) * (a - b)  % (a + b) } + { b^2  % ( a + b) } ] % (a+b) ... using properties of modular arithmetic (refer below link)...
===> { b^2  % ( a + b) ... using {(x*y + z) % x = z % x} from my own understanding but also relates to the link below.
a^2 % (a + b) = b^2  % ( a + b)
a^2 % (a + b) = b^2  ... where (a+b) > b^2
substituting a=10^9 and b=7
10^18 % (10^9 + 7) = 49

Interestingly, above works where b = -7 as well. The given problem can be solved using a modern computer based calculator but knowing this is still useful!

References -

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction