Problem 48

Step 1: Using parity and properties of powers of 2 to simplify the equation. We note that if $2^{x}=2^{y}$ for some real numbers $x$ and $y$, then $x=y$. We examine equations of the form $2^{a}+2^{b}=2^{c}+2^{d}$ where $a, b, c$, and $d$ are integers. We may assume without loss of generality that $a \leq b$ and $c \leq d$ and $a \leq c$. We factor the equation as $2^{a}(1+2^{b-a})=2^{c}(1+2^{d-c})$, and then divide both sides by $2^{a}$ to obtain $1+2^{b-a}=2^{c-a}(1+2^{d-c})$. We show that $c=a$ by contradiction: If $c \neq a$, then $c \geq a$ gives $c>a$. If $c>a$, then $c-a>0$, so $c-a \geq 1$, since $c-a$ is an integer. Therefore, the right side has a factor of $2^{c-a}$, so the right side is even. Thus, the left side is even too, which means that $2^{b-a}$ must be an odd integer. For $2^{b-a}$ to be an odd integer, we must have $2^{b-a}=1$ and so $b-a=0$ or $b=a$. In this case, the left side equals 2 and the right side is greater than 2, since $2^{c-a} \geq 2$ and $1+2^{d-c}>1$. This is a contradiction. Therefore, $c=a$. Since $a=c$, then $2^{a}+2^{b}=2^{c}+2^{d}$ becomes $2^{b}=2^{d}$ and so $b=d$. Therefore, if $2^{a}+2^{b}=2^{c}+2^{d}$ with $a, b, c, d$ integers, then either $a=b=c=d$ or $a=c$ and $b=d$ (with $a \neq b$) or $a=d$ and $b=c$ (with $a \neq b)$. We examine these three possibilities in the given equation, noting that $m, n$ and $k$ are all positive integers: Case 1: $4m^{2}=m^{2}-n^{2}+4=k+4=3m^{2}+n^{2}+k$. From the last equality, we obtain $3m^{2}+n^{2}=4$. Since $m, n$ are positive integers, then $m^{2} \geq 1$ and $n^{2} \geq 1$. Since $3m^{2}+n^{2}=4$, then it must be that $m=n=1$. Thus, $4m^{2}=k+4$ implies $4=k+4$ or $k=0$. But $k>0$, so this case is not possible. Case 2: $4m^{2}=k+4$ and $m^{2}-n^{2}+4=3m^{2}+n^{2}+k$ and $4m^{2} \neq m^{2}-n^{2}+4$. From the second equality, we obtain $2m^{2}+2n^{2}+k=4$, which is not possible since $m, n, k>0$, and so $2m^{2}+2n^{2}+k \geq 5$. Therefore, this case is not possible. Case 3: $4m^{2}=3m^{2}+n^{2}+k$ and $m^{2}-n^{2}+4=k+4$ and $4m^{2} \neq m^{2}-n^{2}+4$. The first equality rearranges to $m^{2}-n^{2}=k$. The second equality also rearranges to $m^{2}-n^{2}=k$. The last statement is equivalent to $3m^{2}+n^{2} \neq 4$. As we saw in Case 1, this means that $(m, n)$ cannot be the pair $(1,1)$, which is consistent with $m^{2}-n^{2}=k$ and $k>0$. Therefore, having examined all of the cases, we have reduced the original problem to finding the number of odd integers $k$ between 0 and 100 for which the equation $m^{2}-n^{2}=k$ has exactly two pairs of positive integers $(m, n)$ that are solutions. Step 2: Connecting solutions to $m^{2}-n^{2}=k$ with factorizations of $k$. We can factor the left side of this equation to give $(m+n)(m-n)=k$. Since $m, n$ and $k$ are positive integers, then $m+n>0$ and $k>0$ so $m-n>0$, or $m>n$. Since $k$ is odd and each of $m+n$ and $m-n$ is an integer, then each of $m+n$ and $m-n$ is odd (since if either was even, then their product would be even). Also, we note that $m+n>m-n$ since $n>0$. Suppose that $(m, n)$ is a solution of the equation $m^{2}-n^{2}=k$ with $m+n=a$ and $m-n=b$ for some odd positive integers $a$ and $b$ with $a>b$. Then $ab=k$, so $ab$ is a factorization of $k$. Therefore, the solution $(m, n)$ corresponds to a specific factorization of $k$. Now suppose that we start with a factorization $k=AB$ where $A$ and $B$ are odd positive integers with $A \geq B$. If we try setting $m+n=A$ and $m-n=B$, then we can add these equations to give $2m=A+B$ (or $m=\frac{1}{2}(A+B)$) and subtract them to give $2n=A-B$ (or $n=\frac{1}{2}(A-B)$). Note that since $n>0$, then $A>B$. Therefore, every factorization of $k$ as the product of two odd positive integers $A$ and $B$ with $A>B$ gives a solution to the equation $m^{2}-n^{2}=k$. Since each solution gives a factorization and each factorization gives a solution, then the number of solutions equals the number of factorizations. Therefore, we have reduced the original problem to finding the number of odd integers $k$ between 0 and 100 which have exactly two factorizations as the product of distinct odd integers $a$ and $b$ with $a>b$. Step 3: Counting the values of $k$. Since $k$ is odd, then all of its prime factors are odd. Since $k<100$, then $k$ cannot have three or more distinct odd prime factors, because the smallest possible product of three distinct odd prime factors is $3 \cdot 5 \cdot 7=105$. Thus, $k$ has two or fewer distinct prime factors. If $k=pq$ for distinct primes $p<q$, then the divisors of $k$ are $1, p, q, pq$, so $k$ has exactly two factorizations of the desired type (namely $1 \cdot pq$ and $p \cdot q$). Since $k<100$ and $p \geq 3$, then $q<\frac{100}{3}$. Since $q$ is an integer, then $q \leq 33$. The odd primes less than 33 are $3,5,7,11,13,17,19,23,29,31$. If $p \geq 11$, then $pq>11^{2}=121$, which is larger than 100. Therefore, $p$ can only be 3,5 or 7. If $p=3$, there are 9 possible values for $q$ (primes from 5 to 31). If $p=5$, there are 5 possible values for $q$ (primes from 7 to 19). If $p=7$, there are 2 possible values for $q$ (11 and 13). Thus, there are $9+5+2=16$ values of $k$ of this form that work. If $k=p^{r}q^{s}$ with $r$ and $s$ positive integers and at least one of $r$ or $s$ is larger than 1, then $k$ will have at least three factorizations. (For example, if $r>1$, then $k=1 \cdot p^{r}q^{s}=p \cdot p^{r-1}q^{s}=p^{r} \cdot q^{s}$ and all of these are distinct.) If $k=p$ or $k=p^{2}$ with $p$ an odd prime, then $k$ has only one factorization as the product of distinct factors ($1 \cdot p$ and $1 \cdot p^{2}$, respectively). Thus, $k$ cannot be of this form. If $k=p^{3}$ with $p$ an odd prime, then the divisors of $k$ are $1, p, p^{2}, p^{3}$, so it has exactly two factorizations of the desired type (namely $1 \cdot p^{3}$ and $p \cdot p^{2}$). Since $k<100$, then $p$ can only equal 3 (because $5^{3}>100$). Thus, there is 1 value of $k$ of this form that works. If $k=p^{4}$ with $p$ an odd prime, then the divisors of $k$ are $1, p, p^{2}, p^{3}, p^{4}$, so it has exactly two factorizations of the desired type (namely $1 \cdot p^{4}$ and $p \cdot p^{3}$). In this case, $k$ has a third factorization, but it is of the wrong type since the two factors will be equal. Since $k<100$, then $p$ can only equal 3 (because $5^{4}>100$). Thus, there is 1 value of $k$ of this form that works. If $k$ has more than 4 factors of $p$, then $k$ will have at least three factorizations of the desired type, so $k$ cannot be of this form. (In particular, if $k=p^{n}$ and $n>4$, then $k=1 \cdot p^{n}=p \cdot p^{n-1}=p^{2} \cdot p^{n-2}$ and these are all distinct since $n-2>2$.) Having examined all of the possible forms, we see that there are $16+1+1=18$ values of $k$ that work, and so there are 18 positive integer solutions to the original equation.