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 n∈Z+n \in \mathbb{Z}^+ be an integer. Its prime factorization is uniquely given by:

n=p1e1p2e2⋯pkek=∏i=1kpiein = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} = \prod_{i=1}^k p_i^{e_i}

where p1<p2<⋯<pkp_1 < p_2 < \dots < p_k are prime numbers, and ei≥1e_i \ge 1 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 n=p1e1p2e2⋯pkekn = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}:

Number of Divisors d(n)d(n): The total count of positive factors is found by choosing an exponent from 00 to eie_i for each prime:

d(n)=(e1+1)(e2+1)⋯(ek+1)d(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1)

Aswell as in similar manner

Sum of Divisors σ(n)\sigma(n): The sum of all positive factors expands into:

σ(n)=(1+p1+⋯+p1e1)(1+p2+⋯+p2e2)⋯(1+pk+⋯+pkek)\sigma(n) = (1 + p_1 + \dots + p_1^{e_1})(1 + p_2 + \dots + p_2^{e_2}) \cdots (1 + p_k + \dots + p_k^{e_k})

Other quick rules you should familiarize with are:

Perfect Squares: An integer nn is a perfect square if and only if every prime exponent eie_i 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:

gcd⁡(a,b)=∏pimin⁡(ei,fi)\gcd(a, b) = \prod p_i^{\min(e_i, f_i)}
lcm⁡(a,b)=∏pimax⁡(ei,fi)\operatorname{lcm}(a, b) = \prod p_i^{\max(e_i, f_i)}

Where a=∏pieia = \prod p_i^{e_i} and b=∏pifib = \prod p_i^{f_i}

Scaffolded Examples

Direct Application (Easy)

Find the total number of positive divisors and the sum of positive divisors of n=180n = 180.

Solution:

First, find prime factorization of 180180 manually

180=18⋅10=(2⋅32)⋅(2⋅5)=22⋅32⋅51180 = 18 \cdot 10 = (2 \cdot 3^2) \cdot (2 \cdot 5) = 2^2 \cdot 3^2 \cdot 5^1

Using the divisor counting formula:

d(n)=(e1+1)(e2+1)(e3+1)=d(180)=(2+1)(2+1)(1+1)=18d(n) = (e_1 + 1)(e_2 + 1)(e_3 + 1)= d(180) = (2 + 1)(2 + 1)(1 + 1) = 18

Using the sum of divisors formula:

σ(n)=(1+2+22)(1+3+32)(1+5)=546\sigma(n) = (1 + 2 + 2^2)(1 + 3 + 3^2)(1 + 5) = 546

So our answers are:

18 and 546\boxed{18 \text{ and } 546}

respectively.

Slightly Harder Problem (Medium)

Find all positive integers nn such that 2n+1212^n + 121 is a perfect square.

Solution:

Suppose 2n+121=m22^n + 121 = m^2 for some positive integer mm.

Rearranging gives a difference of squares:

m2−121=2n  ⟹  (m−11)(m+11)=2nm^2 - 121 = 2^n \implies (m - 11)(m + 11) = 2^n

By unique prime factorization, any factor of a power of 22 must itself be a power of 22.

Let WLOG where a<ba < b and a+b=na + b = n:

m−11=2aandm+11=2bm - 11 = 2^a \quad \text{and} \quad m + 11 = 2^b

Subtracting the two equations eliminates mm:

(m+11)−(m−11)=2b−2a  ⟹  22=2a(2b−a−1)=2⋅11(m + 11) - (m - 11) = 2^b - 2^a \implies 22 = 2^a(2^{b-a} - 1) = 2 \cdot 11

And since b>ab > a, we know 2b−a−12^{b-a} - 1 must be an odd integer. Comparing the even power of 22 and odd factors on both sides:

2a=2  ⟹  2b−1−1=11  ⟹  2b−1=122^a = 2 \implies 2^{b-1} - 1 = 11 \implies 2^{b-1} = 12

Since 1212 is not a power of 22, there are no integer solutions for bb. Thus, there are:

No solutions\boxed{\text{No solutions}}

Olympiad Application (Hard)

Find all pairs of positive integers (a,b)(a, b) such that a2b+a+ba^2b + a + b is divisible by ab2+b+1ab^2 + b + 1.

Solution:

We start by first establishing that bb and ab2+b+1ab^2 + b + 1 are coprime.

Suppose d=gcd⁡(b,ab2+b+1)d = \gcd(b, ab^2 + b + 1). Then d∣bd \mid b, which implies d∣b(ab+1)d \mid b(ab + 1), so d∣(ab2+b)d \mid (ab^2 + b).

Since dd must also divide ab2+b+1ab^2 + b + 1, it must divide their difference:

d∣(ab2+b+1)−(ab2+b)  ⟹  d∣1d \mid (ab^2 + b + 1) - (ab^2 + b) \implies d \mid 1

Thus, gcd⁡(b,ab2+b+1)=1\gcd(b, ab^2 + b + 1) = 1.

Because bb shares no common prime factors with the divisor ab2+b+1ab^2 + b + 1, multiplying the numerator in the given valid fraction ab2+b+1∣a2b+a+bab^2 + b + 1 \mid a^2b + a + b by bb creates an equivalent divisibility relation without introducing extraneous solutions:

ab2+b+1∣a2b+a+b  ⟺  ab2+b+1∣b(a2b+a+b)ab^2 + b + 1 \mid a^2b + a + b \iff ab^2 + b + 1 \mid b(a^2b + a + b)

Working out gives:

ab2+b+1∣a(ab2+b+1)+(b2−a)  ⟹  ab2+b+1∣b2−aab^2 + b + 1 \mid a(ab^2 + b + 1) + (b^2 - a) \implies ab^2 + b + 1 \mid b^2 - a

We now analyze the possible values of b2−ab^2 - a:

Case 1: b2−a=0b^2 - a = 0

  ⟹  a=b2\implies a = b^2; Testing a=b2a = b^2 in the original expression:

a2b+a+b=b5+b2+b=b(b4+b+1)a^2b + a + b = b^5 + b^2 + b = b(b^4 + b + 1)

and

ab2+b+1=b4+b+1ab^2 + b + 1 = b^4 + b + 1

Since b4+b+1∣b(b4+b+1)b^4 + b + 1 \mid b(b^4 + b + 1) holds for all positive integers bb, (b2,b)(b^2, b) is a valid solution family.

Case 2: b2−a>0b^2 - a > 0

For a positive integer to be divisible by another, the dividend must be at least as large as the divisor:

b2−a≥ab2+b+1b^2 - a \ge ab^2 + b + 1

However, since a≥1a \ge 1 and b≥1b \ge 1, we have ab2+b+1>b2>b2−aab^2 + b + 1 > b^2 > b^2 - a, creating a contradiction.

Case 3: b2−a<0b^2 - a < 0

Let a−b2>0a - b^2 > 0 for the sake of contradiction. Divisibility requires:

a−b2≥ab2+b+1  ⟹  a(1−b2)≥b2+b+1a - b^2 \ge ab^2 + b + 1 \implies a(1 - b^2) \ge b^2 + b + 1

Since b≥1b \ge 1, we have (1−b2)≤0(1 - b^2) \le 0, while b2+b+1>0b^2 + b + 1 > 0.

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:

(b2,b) for any strict positive integer b\boxed{(b^2, b) \text{ for any strict positive integer } b }

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 X⋅Y=pkX \cdot Y = p^k and gcd⁡(X,Y)=1\gcd(X, Y) = 1, then one factor must be 11 and the other pkp^k.

-Size Bounds: Use divisibility size inequalities (A∣B  ⟹  ∣A∣≤∣B∣A \mid B \implies \vert{}A\vert{} \le \vert{}B\vert{} for B≠0B \neq 0) to eliminate impossible exponent ranges.

Key Ideas

Simplify messy exponents and seemingly random numbers into their factors to see underlying structure

Practice Problems

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.