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 , sometimes denoted as (pretty much similar to the function), is the smallest positive integer such that .
Also note that , thus . This is more useful when has few prime factors, e.g. .
Also, the existance of primitive roots are pretty important too, which is denoted as and passes through all the numbers in the set .
The v_p argument
Once we get the relation that , it is quite natural to think how many times is divisible by . This motivates us to the following definition.
-Let be prime and define a function as following: If is an integer and is the largest integer such that , then . For , define . By convention we define .
problem: Convince yourself that this definition makes sense.
Let greek letter is read as ``nu'', but people often use the alphabet because they're lazy.
There are a few results about this function.
- and if then the equality holds.
- .
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 be a prime, and , are integers. Suppose that
- ;
- ;
- But .
Then for any positive integer , we have the equation
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 . See https://en.wikipedia.org/wiki/Lifting-the-exponent_lemma for details.
Note that if is odd, we can derive to the equation of by flipping the sign of .
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 be a coprime integers, then for any integer , ``generates a new prime factor'', that is, there exists are prime dividing but not dividing for each . But, with two edge cases as an exception:
- and is a power of .
- .
Similarly,
Statement 2: generates a new prime factor for any with an exception
- .
The Zsigmondy theorem is useful for bounding by prime factors, like in the situation .
Example (USA January TST 2012, this problem is quite silly): Find all positive integers such that for all primes dividing , there exists a positive integer less than such that
Warm-Up Examples
Example 1: LTE Problem
Let be an odd prime. Your goal is to prove that for any positive integer , .
First, we will let and . Note that since , and . Now, since the exponent is a positive integer and is an odd prime, we can simply use LTE directly. We get . Simplifying the right side gives us . By definition, we have proven .
Example 2: LTE Special Case
Your goal is to find all positive integers such that divides .
We will be using the specific -adic version of LTE. Firstly, if is odd, then , which means that . The condition requires , which gives no solutions. Now, if is even, we can simply apply special case LTE for the prime to get . This simplifies to . The divisibility condition requires , which simplifies to . Since , the inequality is impossible for all positive integers . So, sadly, there are NO integer solutions.
Example 3: Zsigmondy!!!
Your job is to find all positive integers such that divides .
First of all, the trivial case clearly works. For , we will let be the smallest prime factor of . Now, since , we must have that . Let , which means that . Furthermore, by FLT, we also know . Because divides , any prime factor of must be strictly less than . However, since and is already defined as the smallest prime factor of , the only way to avoid a contradiction is if . This implies , which means , which is impossible. Therefore, is the only solution.
Example 4: Spicy Problem
Let be coprime positive integers and be a prime such that . If , your job is to determine all possible values for the exponent when is odd.
Because and is an odd prime, we can apply LTE for an odd exponent . If were even, , and since , , meaning , contradiction. Thus, must be odd. Applying LTE for odd gives . We are given that this expression equals . Equating them, and simplifying gives us . So, must be any odd multiple of that is not a multiple of , which can be written as where . :)
Example 5: Another Spicy Problem
Your goal is to prove that has NO integer solutions for .
If , , which is not a pure power of . For , we can use Zsigmondy's Theorem to guarantee that must contain AT LEAST ONE primitive prime divisor because the base pair and do not match the exception. By definition, this primitive prime must satisfy , which meansthat . Therefore, HAS TO be an odd prime factor of . However, now notice that the other side of the equation is , which contains no odd prime factors. So, no solutions can exist for any .
Walkthrough
To be written
| Status | Source | Problem Name | Difficulty | Tags | ||
|---|---|---|---|---|---|---|
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.
