I have the following equation.
$(X + a)^n\equiv(X^n + a)(X^r - 1)\bmod n.$
This is part of the AKS algorithm.
The problem is, that I'll have to solve this equation for every $1\leq a<10$ and $n$ can become quite big. With big I mean at least 100.000.000. So are dealing here with big powers. All numbers are positive Integers and $X$ is a random prime number and $3\leq X\leq 2000$ and is different for every $a$. $r$ is at least $3$ and can become as high as a million.
The question:
I want to know if it is possible to proof this equation without calculating the actual values. (The powers etc...) I don't want the proof just for this equation but for all equations in general, where it would take too long to calculate both parts of the equation and compare the results.
I have no mathematics background or what so ever, so be easy with the terms please :).
What I tried:
Not much, since I have no idea where to start. I have tried to simplify the equation with Wolfram Mathematica, but it gave me the same equation.
If you need more information, please leave a comment.
Thanks in advance,
Mixxiphoid
EDIT:
${X}$ is always a prime.
I edited the first paragraph concerning the meaning of the variables.