Tag Archives: Maths

Prime Counting Function and Chebyshev Bounds

The distribution of primes plays a central role in number theory. The famous mathematician Gauss had conjectured that the number of primes between \(1\) and \(n\) is roughly \(n/\log n\). This estimation gets more and more accurate as \(n\to \infty\). We use \(\pi(n)\) to denote the number of primes between \(1\) and \(n\). So, mathematically, Gauss’s conjecture is equivalent to the claim

\[\lim_{n\to\infty}\frac{\pi(n)}{n/\log n}=1\]

Continue reading Prime Counting Function and Chebyshev Bounds

A Special Case of Zsigmondy’s Theorem

Theorem (Zsigsmondy): 

  1. For two coprime positive integers \(a\) and \(b\) and for any positive integer \(n\), \(a^n-b^n\) has a prime divisor that does not divide \(a^k-b^k\) for all positive integers \(k< n\) with the following exceptions:
    • \(n = 2\) and \(a+b\) is a power of two.
    • \(n=6, a=2, b=1\).
  2. For two coprime positive integers \(a\) and \(b\) and for any positive integer \(n\), \(a^n+b^n\) has a prime divisor that does not divide \(a^k+b^k\) for all positive integers \(k< n\) with the following exception:
    • \(n=3, a=2, b=1\).

This theorem is very helpful in solving many olympiad number theory problems. However, its use is often frowned upon, as this theorem is quite hard to prove using only elementary mathematics. (I am aware of the proof using Cyclotomic Polynomials, but that’s not “elementary enough” in my opinion.)

In olympiad mathematics, one can get away in most of the cases by just using this theorem for a fixed pair of \(n\) and \(k\). This modification allows us to provide a very simple proof using LTE. Here I’ll restate this particular case, and then prove the first part. The second part can be proven analogously.

Theorem (Zsigsmondy Special Case): 

  1. For two coprime positive integers \(a\) and \(b\) and any two positive integers \(n\) and \(k\) with \(k<n\), \(a^n-b^n\) has a prime divisor that does not divide \(a^k-b^k\) with the following exception:
    • \(n = 2, k=1\) and \(a+b\) is a power of two.
  2. For two coprime positive integers \(a\) and \(b\) and any two positive integers \(n\) and \(k\) with \(k<n\), \(a^n+b^n\) has a prime divisor that does not divide \(a^k+b^k\) with the following exception:
    • \(n=3, k=1,a=2, b=1\).

Proof of 1:

Suppose \(a^n-b^n\) and \(a^k-b^k\) share same set of prime divisors. This implies \(a^n-b^n\) and \(a^{\gcd(n,k)}-b^{\gcd(n,k)}\) also share same set of prime divisors. Assuming \(A=a^{\gcd(n,k)}\) and \(B=b^{\gcd(n,k)}\), we could follow the rest of this argument and get to a contradiction. So, without loss of generality, we may assume \(k=1\).

Now we consider two cases:

Case 1: \(n\) is a power of \(2\).
If \(n=2\) and \(a+b\) is a power of two, we arrive at one of the listed exceptions. Now note that,
\(\begin{align*}&\gcd(a+b, a^2+b^2)\\
=&\gcd(a+b, (a+b)^2-a^2-b^2)\\
=&\gcd(a+b,2ab)\\
=&\gcd(a+b,2)\end{align*}\)
This implies both \(a+b\) and \(a^2+b^2\) can’t be powers of two unless \(a+b=2\implies a=b=1\). Hence at least one of them must have an odd prime divisor. Furthermore, this prime divisor does not divide \(a-b\) since \(\gcd(a-b, a^2+b^2)=\gcd(a-b,2)\) (following the previous steps). However, if \(n>2\), then \(a^2+b^2|a^n-b^n\), implying that odd prime will divide \(a^n-b^n\). This is a contradiction.

Case 2: \(n=2^md\) with \(d>1\) being odd.
Without loss of generality, we may assume \(n>1\) is odd, since \(a^d-b^d|a^n-b^n\) and it is sufficient to show that \(a^d-b^d\) has a prime divisor that does not divide \(a-b\).  From LTE, \(v_p(a-b)+v_p(n)=v_p(a^n-b^n)\) for each odd prime \(p|a-b\). Furthermore, \[\frac{a^n-b^n}{a-b}\equiv na^{n-1}\equiv 1\pmod 2\] implying \(v_2(a-b)=v_2(a^n-b^n)\). Therefore, we can conclude \[\frac{a^n-b^n}{a-b}=\prod_{p|\gcd(n,a-b)}p^{v_p(n)}\leq n\] which is impossible for \(n>1\). This raises another contradiction and we are done.