TOPICS
Search

Zsigmondy Theorem


If 1<=b<a and (a,b)=1 (i.e., a and b are relatively prime), then a^n-b^n has at least one primitive prime factor with the following two possible exceptions:

1. 2^6-1^6.

2. n=2 and a+b is a power of 2.

Similarly, if a>b>=1, then a^n+b^n has at least one primitive prime factor with the exception 2^3+1^3=9.

A specific case of the theorem considers the rth Mersenne number M_r=2^r-1, then each of M_2, M_3, M_4, ... has a prime factor that does not occur as a factor of an earlier member of the sequence, except for M_6. For example, M_1, M_2, M_3, ... have the factors 3, 7, 5, 31, (1), 127, 17, 73, 11, 23·89, ... (OEIS A064078) that do not occur in earlier M_n. These factors are sometimes called the Zsigmondy numbers Zs(n,2,1).

Zsigmondy's theorem is often useful, especially in group theory, where it is used to prove that various groups have distinct orders except when they are known to be the same (Montgomery 2001).


See also

Mersenne Number

Explore with Wolfram|Alpha

References

Chabaud, F. and Vaudenay, S. "Links between Differential and Linear Cryptanalysis." EUOROCRYPT 94, pp. 356-365, 1994.Montgomery, H. "Divisibility of Mersenne Numbers." 17 Sep 2001. http://listserv.nodak.edu/scripts/wa.exe?A2=ind0109&L=nmbrthry&P=1635.Ribenboim, P. The Little Book of Big Primes. New York: Springer-Verlag, p. 27, 1991.Sloane, N. J. A. Sequence A064078 in "The On-Line Encyclopedia of Integer Sequences."Zsigmondy, K. "Zur Theorie der Potenzreste." Monatshefte für Math. u. Phys. 3, 265-284, 1882.

Referenced on Wolfram|Alpha

Zsigmondy Theorem

Cite this as:

Weisstein, Eric W. "Zsigmondy Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ZsigmondyTheorem.html

Subject classifications