Kvant Math Problem 437
Let the odd number be
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m38s
Source on kvant.digital
Problem
Prove that an odd number that is the product of $n$ distinct prime factors can be represented as the difference of the squares of two natural numbers in exactly $2^{n-1}$ different ways.
O. Goncharik, S. Sergei
Exploration
Let the odd number be
$$N=p_1p_2\cdots p_n,$$
where the primes $p_i$ are distinct.
A representation of $N$ as a difference of two squares has the form
$$N=x^2-y^2=(x-y)(x+y),$$
with $x>y\ge 0$ integers. Since $N$ is odd, both factors $x-y$ and $x+y$ are odd.
It is natural to begin with small cases.
For $n=1$, let $N=p$. Then
$$p=1\cdot p,$$
hence
$$x=\frac{p+1}{2},\qquad y=\frac{p-1}{2}.$$
This gives one representation. Since $p$ has only the factorization $1\cdot p$ into positive odd factors, there is no other one. The number of representations is $1=2^{1-1}$.
For $n=2$, let $N=pq$. The positive odd factorizations are
$$1\cdot pq,\qquad p\cdot q.$$
They produce two representations, agreeing with $2^{2-1}=2$.
The counting evidently reduces to counting factorizations $N=ab$ with $a$ and $b$ odd. Because the prime factors are distinct, every divisor is obtained by choosing a subset of the primes. There are $2^n$ divisors. If ordered pairs $(a,b)$ with $ab=N$ are counted, there are $2^n$ such pairs. Each representation by squares corresponds to exactly one unordered factorization ${a,b}$, since $a=x-y$ and $b=x+y$. The only point requiring care is to prove that every unordered factorization indeed yields a unique pair $(x,y)$ of natural numbers and that different factorizations cannot lead to the same representation.
The crucial step is establishing a bijection between representations
$$N=x^2-y^2$$
and unordered factorizations of $N$ into positive odd factors.
Problem Understanding
We are given an odd integer
$$N=p_1p_2\cdots p_n,$$
where the primes $p_1,\dots,p_n$ are distinct. We must prove that the number of representations
$$N=x^2-y^2$$
by natural numbers $x$ and $y$ is exactly $2^{n-1}$.
This is a Type B problem, a pure proof.
The core difficulty is counting the representations without omission or duplication. That requires a precise correspondence between representations as a difference of squares and factorizations of $N$ into two positive odd factors.
Proof Architecture
Lemma 1. A representation $N=x^2-y^2$ determines the factorization $N=(x-y)(x+y)$ into positive odd factors.
Sketch: Since $N$ is odd, $x-y$ and $x+y$ have the same parity and their product is odd, hence both are odd.
Lemma 2. Every factorization $N=ab$ into positive odd factors with $a\le b$ determines a unique representation $N=x^2-y^2$.
Sketch: Set $x=(a+b)/2$ and $y=(b-a)/2$; oddness of $a$ and $b$ makes these integers, and then $x^2-y^2=ab$.
Lemma 3. The correspondence of Lemmas 1 and 2 is bijective between representations and unordered factorizations ${a,b}$ of $N$.
Sketch: The formulas are inverse to each other.
Lemma 4. The number of unordered factorizations of $N$ equals $2^{n-1}$.
Sketch: Each divisor corresponds to a choice of a subset of the $n$ distinct primes, giving $2^n$ ordered factorizations. Since $N$ is not a square, no factorization satisfies $a=b$, and each unordered factorization corresponds to exactly two ordered ones.
The hardest direction is proving the counting in Lemma 4 without double-counting.
Solution
Let
$$N=p_1p_2\cdots p_n,$$
where $p_1,\dots,p_n$ are distinct odd primes.
Suppose first that
$$N=x^2-y^2$$
for natural numbers $x>y$. Then
$$N=(x-y)(x+y).$$
Since $N$ is odd, the factors $x-y$ and $x+y$ are both odd. Thus every representation of $N$ as a difference of two squares yields a factorization of $N$ into two positive odd factors.
Conversely, let
$$N=ab$$
be a factorization into positive odd factors, and assume $a\le b$. Define
$$x=\frac{a+b}{2},\qquad y=\frac{b-a}{2}.$$
Because $a$ and $b$ are odd, both $x$ and $y$ are integers. Moreover,
$$x-y=a,\qquad x+y=b.$$
Hence
$$x^2-y^2=(x-y)(x+y)=ab=N.$$
Thus every factorization of $N$ into positive odd factors produces a representation of $N$ as a difference of two squares.
The two constructions are inverse to each other. Starting from a representation, we recover the factors $a=x-y$ and $b=x+y$. Starting from a factorization, we recover $x$ and $y$ from the formulas above. Therefore there is a bijection between representations
$$N=x^2-y^2$$
and unordered factorizations of $N$ into positive odd factors.
It remains to count these factorizations.
Since the primes $p_1,\dots,p_n$ are distinct, every divisor of $N$ has the form
$$p_{i_1}p_{i_2}\cdots p_{i_k},$$
where the chosen primes constitute a subset of ${p_1,\dots,p_n}$. There are exactly $2^n$ such subsets, hence exactly $2^n$ divisors.
Each divisor $d$ determines an ordered factorization
$$N=d\cdot \frac{N}{d}.$$
Therefore there are $2^n$ ordered factorizations of $N$.
Because all prime factors of $N$ occur with exponent $1$, the number $N$ is not a square. Consequently no factorization satisfies
$$a=b.$$
Thus every unordered factorization ${a,b}$ corresponds to exactly two ordered factorizations,
$$(a,b)\quad\text{and}\quad(b,a).$$
Hence the number of unordered factorizations equals
$$\frac{2^n}{2}=2^{,n-1}.$$
By the established bijection, the number of representations of $N$ as a difference of the squares of two natural numbers is also
$$2^{,n-1}.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the passage from a representation to a factorization. If
$$N=x^2-y^2,$$
then
$$N=(x-y)(x+y).$$
Since $N$ is odd, both factors must be odd. A careless argument might merely state that $x-y$ and $x+y$ have the same parity. That alone is insufficient. Their product being odd forces each factor individually to be odd.
The second delicate point is recovering $x$ and $y$ from a factorization. Given odd factors $a\le b$, the formulas
$$x=\frac{a+b}{2},\qquad y=\frac{b-a}{2}$$
produce integers because the sum and difference of two odd numbers are even. Without the oddness condition, these quantities need not be integral.
The third delicate point is the division by two in the counting argument. This is valid only because no unordered factorization is fixed by exchanging its factors. Such a fixed point would require $a=b$, hence $N=a^2$. Since every prime divisor of $N$ occurs with exponent $1$, $N$ is not a square. Therefore each unordered factorization corresponds to exactly two ordered ones.
Alternative Approaches
One may count directly through subsets of the prime factors. Choose any subset $S$ of ${p_1,\dots,p_n}$ and let
$$a=\prod_{p_i\in S}p_i,\qquad b=\frac{N}{a}.$$
Then
$$x=\frac{a+b}{2},\qquad y=\frac{|b-a|}{2}$$
gives a representation $N=x^2-y^2$. Two complementary subsets produce the same pair ${a,b}$ and hence the same representation. Since there are $2^n$ subsets and complementary subsets come in pairs, the number of representations is $2^{n-1}$.
The main proof is preferable because it first establishes a clean bijection between representations and factorizations. Once that correspondence is in place, the counting becomes completely transparent.