Fork me on GitHub
Math for the people, by the people.

User login

An Indirect Primality Test

Primary tabs

An Indirect Primality Test


For the sake of this post I will confine myself to numbers with the shape

x^2 + 1.

Preliminary remarks: 1) I am certain about this being a valid test.

2) This is not a probabality test;
3) I doubt whether it is a comparitively efficient test when the suspects
are very large. Members' opinions invited..

4)_ A property of polynomial functions: Let f(x) be a polynomial in x ( x
belongs to Z), Then f(x + k*f(x)) is congruent to 0 (mod f(x)).
Here k belongs to N. This can be proved by Taylor's theorem.

At this stage I would prefer to use failure function terminology:
Definition of failure: A composite number
Definition of failure function ( in the present context). x = x_0 + k*f(x_0)) =x_0 + k*(x_0^2+1) ; here x_0 is a specific value of x. This is because x = (x_0 + k*f(x_0)) , when substituted in f(x), results in failures (composites) exactly divisible by f(x_0).

Numerical illustration: Let x_0 = 4. f(x_0) = 4^2 + 1 = 17; x = 4 + k*17 generates values of x
such that f(x_0) is composite ( all multiples of 17).
Note: Whenever f(x) is composite each factor contributes a failure function.
An important observation: whenever a number with the shape of a quadratic cyclotomic expression is composite, the relevant x MUST satisfy a prior failure function. This is because a composite number with the shape of a quadratic cyclotomic polynomial has one factor less than the relevant x. Hence the indirect test consists of just generating values of x by the prior failure functions and checking whether x_0
(where x_0^2 + 1 is the large prime suspect) is generated by one or more of these failure functions.

A numerical illustration of the logic: 99994^2 + 1 is prime because 99994 is not generated by any of the failure functions for 1 < x < 99994. On the other hand 12^2 + 1 =145 is composite since 12 is generated by the f.f. x = 2 + 5*k.

It may be possible to write a program that programs the failure functions and also checks whether a given x_0 is generated by these functions or not.

Dear Daniel,
This is not a counter example since 34 is generated by the f.f. 5 + 13*k when k = -3. (Kindly note k belongs to Z and not N as stated by me - I will make the necessary amendment). Hence we get 5 + 13(-3) = -34 and (-34)^2 + 1 = 1157. In fact I wd be very much surprised if anyone can find a counter example.

Now pl note that modulus 13 is less than modulus 34; hence modulus 34 has to be predicted by the failure function when x reaches
the stage 5 i.e. 5 + 13*k where k belongs to Z.

In other words since in the case of composites with the shape of quadratic cyclotomic expresions , the absolute value of atleast one of the factors has to be smaller than the the relevant x.

Trust I have made myself clear.


Dear Daniel,
Let me give another f.f. which generates 34:x = 8 + 13*k

(8^2 + 1 = 65 = 5*13; recall that each factor contributes a f.f.)

Dear Devaraj,

I am starting to understand (slowly), thanks to your examples. I am resuming your argument, in simple terms (please avoid mentioning "failure functions", that makes me feel like a total failure...).

Let P = X^2 + 1 where X is an integer in Z.
If there exists a pair A and K in Z satisfying condition 1:

X = A + K(A^2 + 1) (condition 1)

Then P is composite.

The converse is not true: 1157 = 34^2 + 1 = 13 * 89 and there exists no pair in Z satisfying condition 1 for X = 34.

However, there is a weaker condition - If there exists a pair A and K in Z satisfying condition 2:

X = A + KP and P is a divisor of A^2 + 1 (condition 2)

Then P is composite.

X = 34 falls into this category. Is the converse generally true? It seems to be self-evident for you, it is not for me. Can you produce a proof here, or give a relevant link?

Meanwhile I'll try to fix my search program for a counter-example.

If your argument is correct (and I guess it is), then it can provide an unprecedented efficient algorithm to test primality, since any number can be written under the form x^n + m, and it seems that your test is valid for this general case (provided it is for x^2 + 1).


Forget the proof, I got it! As it happens many times, I woke up this morning and eureka!
It is indeed self-evident and I am not going to waste time searching for a counter-example which doesn't exist, now I am convinced. Your test is a real achievement since it works for any polynom of the kind x^n + m. Next week I am going to invest some time in trying to implement a computer algorithm. The strategy would be, for a given number P to test, to find an exponent n such that P = x^n + m and have a minimum of trials on x. Any better idea?

Dear Daniel,

You must forgive me for replying to you so late; the fact is I have not been visiting PM for about a year.

My first q: Could you find a counter example ?

Secondly: I will be glad if you would try to comprehend failure function terminology. In case you succeed then both of us would be talking the same language and so understanding each other
would be much easier. If required I would be only too happy to explain it.

Second q: My old yahoo id got eaten up by a virus and so I am not able to automatically receive notices/mail sent to me by PM members. I tried to change my setting but could not; what do you suggest?
A.K. Devaraj

Dear Devaraj,

Apparently you didn't not see my last note about this subject. I finally followed your idea, using simple polynomial algebra, and understood that you are right. So I didn't waste time looking for a counter example which doesn't exist, now I am convinced.

While I can understand that failure function theory provides shortcuts to prove many algebra theorems, I think that I am too old to learn this subject. I am retired and quite busy with other things.

I think that you should write an entry at PM on this subject, for two reasons:

1 - The test in itself is absolutely remarkable.

2 - The use of a failure function to prove it, shows the power of the theory.

Perhaps you would be interested to know that I am in my 80th year; biological age is more or les meaningless.

Dear Permalink-you are right about bio-age; I am 85.

Hi akdevaraj,

I think that your test is only a partial test, or I am missing something. If a suspect of the form P = X^2 + 1 satisfy your criterion, then it is certainly a composite number, but if it doesn't, it could also be a composite number.

Since my knowledge in algebra is very elementar, I am going to re-formulate your criterion with my own words, and please correct me if I am wrong.

1 - If there exists a couple K in N and A in Z such that:
X = A + K(A^2 + 1)
then P is composite. I agree, proof by Taylor.

2 - Do you claim that the converse is also true? that is, if P is composite there exists such a couple? In that case I have a counter-example (found by computer search):

1157 = 34^2 + 1 = 13 * 89


Kindly note that in point 4 above, k belongs to Z and not N. The oversight is regreted.

Hi akdevarad, may you please explain me, rigurously, how do the function f(x+K*f(x)) (you don’t explain what * means), containing as argument the proper function, could be congruent to 0 (mod f(x))? For sure your sentence needs a lot of rigurous mathematical explanation.

Dear Peruchio - f(x+k*f(x)) - star means ”multiply”. k belongs to Z Thus in this case since f(x) = x^2+x+1, f(x+k*f(x)) means 1 + 3k. Trust this is clear.

Thanks akdevaraj for clarify what "*" means. k* confused me since here in PM one simply writes f(x+kf(x)). Your example is quite complex, so f(x+kf(x)) is too long. But let's suppose f(x)=x^2, so f(x+kf(x))=f(x+kx^2)=(x+kx^2)^2=k^2x^4+2kx^3+x^2.
Let's prove a couple of examples. If k=0, f(x+0f(x))=0^2x^4+2(0)x^3+x^2=x^2=f(x) as it should be. If k=1, f(x+1f(x))=1^2x^4+2(1)x^3+x^2=x^2+2x^3+x^4=(x+x^2)^2=f(x+x^2), again as it should be. Thus I can't understand what you are trying to do. Greetings.

Dear dh2718, thanks for the compliment.

Currently reading ”prime numbers - a computational perspective” by Richard Crandall and Carl Pomerance.

This is a monumental book on prime numbers, primality testing and factorisation.

Currently reading ”prime numbers - a computational perspective” by Richard Crandall and Carl Pomerance.

This is a monumental book on prime numbers, primality testing and factorisation.

Currently reading ”prime numbers - a computational perspective” by Richard Crandall and Carl Pomerance.

This is a monumental book on prime numbers, primality testing and factorisation.

(a/p) is the Legendre symbol for quadratic residues and non-residues. If (a/p) = -1 it means a is not a quadratic residue of p. Another way of expressing this: the p (under ref ) is an impossible prime factor of (x^2 - a ).For further examples of this concept see A123239, A 072936 and A 119691 on OEIS.

Search engine still not functioning!

Subscribe to Comments for "An Indirect Primality Test"