Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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,

${X}$ is always a prime.
I edited the first paragraph concerning the meaning of the variables.

share|cite|improve this question
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
@alex.jordan != is how I use it in the equation, the opposite is the same to me. % is indeed module. r is an Integer with a minimal value of 3. – Mixxiphoid Nov 11 '12 at 21:51
It would be appreciated if you adapt your wording and your layout to the conventions of mathematics and of this forum. – miracle173 Nov 12 '12 at 7:52
@miracle173 could you please help me with that? I did my best, but as noted in the post, I have no mathematics background. Feel free to edit any thing. – Mixxiphoid Nov 12 '12 at 7:56
I took a look at the wikipedia article. Should your relation be the if-condition in step 5 of the algorithm in the article? This would not be the case as far as I can see. The X in this algorithm is a variable and not an integer number. Did you notice that there is also a link to implementation details for the algorithm that points to article? There are probabilistic primaltity tests that are much easier to implement than the AKS algorithm like the Miller-Rabin test. – miracle173 Nov 12 '12 at 18:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.