# How to proof this equation without calculating the values it self

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.

${X}$ is always a prime.
I normally read "!=" to mean not equals. Is that your intent? Also, does "% n" mean modulo $n$? Lastly, what is $r$? Do you intend somethng to be true for all values of $n$ and $r$? – alex.jordan Nov 11 '12 at 18:32