Overview

In this section we'll be dealing with variable on exponents, using LTE, Zsigmondy, etc. to solve the problem.

Orders (review)

This should be a review for most of you. The order of a(modp)a\pmod p, sometimes denoted as ordp(a)\text{ord}_p (a) (pretty much similar to the log⁡\log function), is the smallest positive integer mm such that am≡1(modp)a^m\equiv 1\pmod p.

Also note that ap−1≡1(modp)a^{p-1}\equiv 1\pmod p, thus ordp(a)∣p−1\text{ord}_p (a)\mid p-1. This is more useful when p−1p-1 has few prime factors, e.g. p=22k+1p=2^{2^k}+1.

Also, the existance of primitive roots are pretty important too, which is denoted as gg and g0,g1,…,gp−1g^0, g^1, \dots, g^{p-1} passes through all the numbers in the set {1,2,…,p−1}\{1, 2, \dots, p-1\}.

The v_p argument

Once we get the relation that p∣mp\mid m, it is quite natural to think how many times mm is divisible by pp. This motivates us to the following definition.

-Let pp be prime and define a function νp ⁣:Q↦Z\nu_p\colon \mathbb{Q}\mapsto \mathbb{Z} as following: If nn is an integer and ee is the largest integer such that pe∣np^e\mid n, then νp(n)=e\nu_p (n)=e. For n=a/bn=a/b, define νp(n)=νp(a)−νp(b)\nu_p (n)=\nu_p (a)-\nu_p (b). By convention we define νp(0)=∞\nu_p (0)=\infty.

problem: Convince yourself that this definition makes sense.

Let greek letter ν\nu is read as ``nu'', but people often use the alphabet vv because they're lazy.

There are a few results about this function.

  • νp(x+y)≥min⁡{νp(x),νp(y)}\nu_p (x+y)\ge \min \{\nu_p(x), \nu_p (y)\} and if νp(x)≠νp(y)\nu_p (x)\ne \nu_p (y) then the equality holds.
  • νp(xy)=νp(x)+νp(y)\nu_p (xy)=\nu_p (x)+\nu_p (y).

Try to prove these results, as it's not really hard.

Lifting Exponents

The v_p function is not going to be good at most problems with only the above results. In fact, there are one more nice property of this function: the Lifting The Exponents lemma, often abbreviated as LTE.

definition. Let pp be a prime, and aa, bb are integers. Suppose that

  • p>2p>2;
  • p∤a,bp\nmid a, b;
  • But p∣a−bp\mid a-b.

Then for any positive integer nn, we have the equation

νp(an−bn)=νp(a−b)+νp(n).\nu_p (a^n-b^n)=\nu_p (a-b)+\nu_p (n).

Always don't forget to confirm this three condition! It's really easy to mess up since each looks like an edge case.

This time, the proof is not going to be that easy and it is proven by induction on nn. See https://en.wikipedia.org/wiki/Lifting-the-exponent_lemma for details.

Note that if nn is odd, we can derive to the equation of νp(an+bn)\nu_p (a^n+b^n) by flipping the sign of bb.

Zsigmondy theorem

Next, we have the Zsigmondy theorem, which is also quite mondatory for some intermediate-to-above level problems. There are two versions but they're essentially the same. The statement is:

Statement 1: Let a>b>0a>b>0 be a coprime integers, then for any integer n>1n>1, an−bna^n-b^n ``generates a new prime factor'', that is, there exists are prime dividing an−bna^n-b^n but not dividing ak−bka^k-b^k for each n>kn>k. But, with two edge cases as an exception:

  • n=2n=2 and a+ba+b is a power of 22.
  • (a,b,n)=(2,1,6)(a, b, n)=(2, 1, 6).

Similarly,

Statement 2: an+bna^n+b^n generates a new prime factor for any n>1n>1 with an exception

  • (a,b,n)=(2,1,3)(a, b, n)=(2, 1, 3).

The Zsigmondy theorem is useful for bounding by prime factors, like in the situation mn=ak−bkm^n=a^k-b^k.

Example (USA January TST 2012, this problem is quite silly): Find all positive integers a,n≥1a, n\ge 1 such that for all primes pp dividing an−1a^n-1, there exists a positive integer mm less than nn such that p∣am−1p\mid a^m-1

Warm-Up Examples

Example 1: LTE Problem

Let pp be an odd prime. Your goal is to prove that for any positive integer nn, pn∥(p+1)pn−1−1p^n \parallel (p+1)^{p^{n-1}} - 1.

First, we will let x=p+1x = p+1 and y=1y = 1. Note that p∣(x−y)p \mid (x-y) since (p+1)−1=p(p+1) - 1 = p, and p∤x,yp \nmid x, y. Now, since the exponent k=pn−1k = p^{n-1} is a positive integer and pp is an odd prime, we can simply use LTE directly. We get vp((p+1)pn−1−1)=vp((p+1)−1)+vp(pn−1)v_p((p+1)^{p^{n-1}} - 1) = v_p((p+1) - 1) + v_p(p^{n-1}). Simplifying the right side gives us vp(p)+(n−1)=1+n−1=nv_p(p) + (n-1) = 1 + n - 1 = n. By definition, we have proven pn∥(p+1)pn−1−1p^n \parallel (p+1)^{p^{n-1}} - 1.

Example 2: LTE Special Case

Your goal is to find all positive integers nn such that 2n+22^{n+2} divides 3n−13^n - 1.

We will be using the specific 22-adic version of LTE. Firstly, if nn is odd, then 3n−1≡2(mod4)3^n - 1 \equiv 2 \pmod 4, which means that v2(3n−1)=1v_2(3^n - 1) = 1. The condition requires 1≥n+21 \ge n+2, which gives no solutions. Now, if nn is even, we can simply apply special case LTE for the prime 22 to get v2(3n−1)=v2(3−1)+v2(3+1)+v2(n)−1v_2(3^n - 1) = v_2(3-1) + v_2(3+1) + v_2(n) - 1. This simplifies to 1+2+v2(n)−1=v2(n)+21 + 2 + v_2(n) - 1 = v_2(n) + 2. The divisibility condition requires v2(n)+2≥n+2v_2(n) + 2 \ge n + 2, which simplifies to v2(n)≥nv_2(n) \ge n. Since 2v2(n)≤n2^{v_2(n)} \le n, the inequality n≤v2(n)n \le v_2(n) is impossible for all positive integers nn. So, sadly, there are NO integer solutions.

Example 3: Zsigmondy!!!

Your job is to find all positive integers nn such that n2n^2 divides 2n−12^n - 1.

First of all, the trivial case n=1n=1 clearly works. For n>1n > 1, we will let pp be the smallest prime factor of nn. Now, since n2∣2n−1n^2 \mid 2^n - 1, we must have that p∣2n−1p \mid 2^n - 1. Let d=ordp(2)d = \text{ord}_p(2), which means that d∣nd \mid n. Furthermore, by FLT, we also know d∣p−1d \mid p-1. Because dd divides p−1p-1, any prime factor of dd must be strictly less than pp. However, since d∣nd \mid n and pp is already defined as the smallest prime factor of nn, the only way to avoid a contradiction is if d=1d = 1. This implies 21≡1(modp)2^1 \equiv 1 \pmod p, which means p∣1p \mid 1, which is impossible. Therefore, n=1n=1 is the only solution.

Example 4: Spicy Problem

Let a,ba, b be coprime positive integers and pp be a prime such that p∣a+bp \mid a+b. If vp(an+bn)=vp(a+b)+1v_p(a^n + b^n) = v_p(a+b) + 1, your job is to determine all possible values for the exponent nn when pp is odd.

Because p∣a+bp \mid a+b and pp is an odd prime, we can apply LTE for an odd exponent nn. If nn were even, an+bn≡2an(modp)a^n + b^n \equiv 2a^n \pmod p, and since gcd⁡(a,b)=1\gcd(a,b)=1, p∤ap \nmid a, meaning vp(an+bn)=0v_p(a^n+b^n) = 0, contradiction. Thus, nn must be odd. Applying LTE for odd nn gives vp(an+bn)=vp(a+b)+vp(n)v_p(a^n + b^n) = v_p(a+b) + v_p(n). We are given that this expression equals vp(a+b)+1v_p(a+b) + 1. Equating them, and simplifying gives us vp(n)=1v_p(n) = 1. So, nn must be any odd multiple of pp that is not a multiple of p2p^2, which can be written as n=p⋅kn = p \cdot k where gcd⁡(k,2p)=1\gcd(k, 2p) = 1. :)

Example 5: Another Spicy Problem

Your goal is to prove that 7n−5n=2k7^n - 5^n = 2^k has NO integer solutions for n>1n > 1.

If n=2n=2, 72−52=247^2 - 5^2 = 24, which is not a pure power of 22. For n>2n > 2, we can use Zsigmondy's Theorem to guarantee that 7n−5n7^n - 5^n must contain AT LEAST ONE primitive prime divisor pp because the base pair (7,5)(7,5) and nn do not match the (2,1,6)(2,1,6) exception. By definition, this primitive prime pp must satisfy p∤(71−51)p \nmid (7^1 - 5^1), which meansthat p∤2p \nmid 2. Therefore, pp HAS TO be an odd prime factor of 7n−5n7^n - 5^n. However, now notice that the other side of the equation is 2k2^k, which contains no odd prime factors. So, no solutions can exist for any n>1n > 1.

Walkthrough

To be written

StatusSourceProblem NameDifficultyTags

Module Progress:

Join the Discord Community!

Stuck on a problem, or don't understand a module? Join the Discord and get help with your doubts while making more math friends.