The Intuition Prime Factor and Exponent Methods
One of the most fundamental rules of arithmetic guarantees that every nonzero positive integer (excluding 1) can be uniquely factored into a product of prime numbers and their powers.
This is very often the starting point of working on a math competition problem because you dig into the core components of elements you are working with to better understand them.
Formal Definitions and Notation
The defintion of the fundamental theorem of arithmetic is:
Let be an integer. Its prime factorization is uniquely given by:
where are prime numbers, and are positive integer exponents.
Another basic function that you should know is one for counting the amount of divisors it has by choosing every possible combination of prime factors; for the integer defined as :
Number of Divisors : The total count of positive factors is found by choosing an exponent from to for each prime:
Aswell as in similar manner
Sum of Divisors : The sum of all positive factors expands into:
Other quick rules you should familiarize with are:
Perfect Squares: An integer is a perfect square if and only if every prime exponent in its prime factorization is even.
The same rule holds for cubes and so on but with their respective power divisiblity.
GCD and LCM via Prime Factorization:
Where and
Scaffolded Examples
Direct Application (Easy)
Find the total number of positive divisors and the sum of positive divisors of .
Solution:
First, find prime factorization of manually
Using the divisor counting formula:
Using the sum of divisors formula:
So our answers are:
respectively.
Slightly Harder Problem (Medium)
Find all positive integers such that is a perfect square.
Solution:
Suppose for some positive integer .
Rearranging gives a difference of squares:
By unique prime factorization, any factor of a power of must itself be a power of .
Let WLOG where and :
Subtracting the two equations eliminates :
And since , we know must be an odd integer. Comparing the even power of and odd factors on both sides:
Since is not a power of , there are no integer solutions for . Thus, there are:
Olympiad Application (Hard)
Find all pairs of positive integers such that is divisible by .
Solution:
We start by first establishing that and are coprime.
Suppose . Then , which implies , so .
Since must also divide , it must divide their difference:
Thus, .
Because shares no common prime factors with the divisor , multiplying the numerator in the given valid fraction by creates an equivalent divisibility relation without introducing extraneous solutions:
Working out gives:
We now analyze the possible values of :
Case 1:
; Testing in the original expression:
and
Since holds for all positive integers , is a valid solution family.
Case 2:
For a positive integer to be divisible by another, the dividend must be at least as large as the divisor:
However, since and , we have , creating a contradiction.
Case 3:
Let for the sake of contradiction. Divisibility requires:
Since , we have , while .
A non-positive quantity cannot be greater than or equal to a positive quantity, so no solutions exist here.
Thus, the complete set of solutions is:
Reference Guide
Exponent manipulation and prime decomposition allow you to reduce high-degree polynomial expressions and complex divisibility statements down to fundamental properties of prime integer factors.
Important usages are Prime Factorization Identities:
-Divisor Count and Divisor sum as seen above.
What is also useful are Algebraic & Bounding Techniques:
-Algebraic Factorization like difference of perfect squares can reveal underlying structures formed by prime factors.
-Coprime Component Splitting: If and , then one factor must be and the other .
-Size Bounds: Use divisibility size inequalities ( for ) to eliminate impossible exponent ranges.
Key Ideas
Simplify messy exponents and seemingly random numbers into their factors to see underlying structure
Practice Problems
| 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.
