How to evaluate below expression of modular arithmetic? How to evaluate (10^18)%(10^9 + 7) using modular arithmetic? How to proceed and what will be the steps?
 A: (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.

A: 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}$.
A: 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
