View Single Post
Old 2017-05-30, 10:43   #4
devarajkandadai's Avatar
May 2004

1001111002 Posts

Originally Posted by axn View Post
x+k*f(x) == x (mod f(x))

==> f(x+k*f(x)) == f(x) (mod f(x)). QED

Looks like a trivial result.
Agreed the result is not earth-shaking. However it has a couple of interesting applications, one of which I would like to mention in this post:

Indirect primality testing. Let f(x) be a quadratic polynomial in x ( x belongs to Z).
For example let f(x) be x^2 + x +1. All x, other than those generated by 1 + 3k, 2 + 7k, 3 + 13k, 4 + 3k and 4 + 7k, 5 + 31k.....are such that f(x) is prime which need not be tested for primality. Unfortunately this is true only upto quadratic level.
devarajkandadai is offline   Reply With Quote