## Prime factorization

#### Problems

- Six consecutive numbers
- Two variables one equation
- Number of divisors
- Number of divisors II
- Prime factorization and perfect squares again
- Prime factorization and divisibility
- When is \(a^2-a\) divisible by 10000?
- Primes in an algebraic equation ＊

### Six consecutive numbers

B3, 2011

Prove that there are infinitely many perfect squares that can be written as a sum of six consecutive natural numbers. Find the smallest such square.

## Solution

The sum of six consecutive numbers is of the form:

\[ \frac{(n+6)(n+7)}{2} - \frac{n(n+1)}{2} \text{ for some } n\]

The above expression simplifies to \(3(2n+7)\). This number is a perfect square whenever \(2n+7=3k^2\). Any odd number greater than one can be substituted for \(k\). The smallest value of \(k\) is 3, so the smallest such square is 81.

\[ 81 = 11+12+\cdots+16 \]

### Two variables one equation

C1, 2011

Show that there are exactly 16 pairs of integers \((x,y)\) such that \(11x+8y+17=xy\).

## Solution

An equation of the form \(xy=ax+by+c\) can be written as:

\[ (x-a)(y-b) = c+ab \]

So the given equation is:

\[ (x-8)(y-13) = 105 \]

The number of solutions to the above equation is the number of divisors of 105. We can factorize 105 as \( 1\cdot 3\cdot 5\cdot 7\). Every subset of these four numbers corresponds to a divisor, so there are \(2^4=16\) solutions.

### Number of divisors

A1, 2019

For a natural number \(m,\) define \(\Phi_{1}(m)\) to be the number of divisors of \(m\) and for \(k \geq 2\) define \(\Phi_{k}(m):=\Phi_{1}\left(\Phi_{k-1}(m)\right) .\) For example, \(\Phi_{2}(12)=\Phi_{1}(6)=4 .\) Find the minimum \(k\) such that

\[ \Phi_{k}\left(2019^{2019}\right)=2 \]

## Solution

A number \(n\) that has prime factorizaton \( p_1^{k_1} p_2^{k_2}\ldots p_t^{k_t} \) has \( (k_1+1)(k_2+1)\ldots(k_t+1) \) divisors.

Iteration | Number | Factorization | Result |
---|---|---|---|

1 | \(2019^{2019}\) | \(3^{2019}\cdot 673^{2019}\) | \(2020^2 \) |

2 | \(2020^2 \) | \(2^4\cdot 5^2\cdot 101^2 \) | \(45 \) |

3 | \(45 \) | \(3^2\cdot 5 \) | \(6 \) |

4 | \(6 \) | \(3\cdot 2 \) | \(4 \) |

5 | \(4 \) | \(2^2 \) | \(3 \) |

6 | \(3 \) | \(3 \) | \(2 \) |

*Comment. A bit tedious task for a first problem. Is there a simpler way?*

### Number of divisors II

A8, 2020

Find the number of positive integers \(n\leq 60\) having \(6\) divisors.

## Solution

Suppose the prime factorization of \(n\) is \(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\), then \(n\) has \( (a_1+1)(a_2+1)\cdots (a_k+1) \) factors. If \(n\) has six factors, its prime factorizaton must be of the form \(p_1p_2^{2}\) or \(p_1^5\). There are nine numbers less than 60 that satisfy this condition:

\[ 2\cdot3^2, 2\cdot 5^2, 3\cdot2^2, 5\cdot 2^2, 5\cdot 3^2, 7\cdot 2^2, 11\cdot 2^2, 13\cdot 2^2 \mbox{ and } 2^{5} \]

### Prime factorization and perfect squares again

B3, 2013

A positive integer \(N\) has its first, third and fifth digits equal and its second, fourth and sixth digits equal. In other words, when written in the usual decimal system it has the form \(x y x y x y,\) where \(x\) and \(y\) are the digits. Show that \(N\) cannot be a perfect power, i.e., \(N\) cannot equal \(a^{b},\) where \(a\) and \(b\) are positive integers with \(b>1\).

## Solution

We have: \[N=\left(10^{5}+10^{3}+10\right) x+\left(10^{4}+10^{2}+1\right) y=10101(10 x+y)= 3 \times 7 \times 13 \times 37 \times(10 x+y)\]

Therefore for \(N\) to be a perfect power, the primes 3,7,13,37 must all occur as factors in the prime factorization of \(10 x+y .\) In particular \(10 x+y \geq 10101\). But since \(x\) and \(y\) are digits, each is between 0 and \(9,\) so \(10 x+y \leq 99\). So \(N\) cannot be a perfect power.

### Prime factorization and divisibility

A6, 2014

Find the smallest \(n\) for which \(\displaystyle \frac{50!}{24^n} \) is *not* an integer.

## Solution

The expression will not be an integer if and only if the numerator has a prime power lesser than the corresponding power in the denominator.

We have \( 24=2^3\cdot 3\). Let us find the the powers of 2 and 3 in \(50!\).

The power of 2 is given by: \[ \lfloor 50/2 \rfloor + \lfloor 50/4 \rfloor + \lfloor 50/8 \rfloor + \lfloor 50/16 \rfloor + \lfloor 50/32 \rfloor = 47 \]

The power of 3 is given by:

\[ \lfloor 50/3 \rfloor + \lfloor 50/9 \rfloor + \lfloor 50/27 \rfloor = 22 \]

The numerator is of the form: \( 2^{47}3^{22}\cdot k \). If \(n=16\), the denominator has \(2^{48}\) as a factor which is sufficient to make the number a non-integer.

### When is \(a^2-a\) divisible by 10000?

B3, 2015

(a) Show that there are exactly 2 numbers \(a\) in \(\{2,3, \ldots, 9999\}\) for which \(a^{2}-a\) is divisible by \(10000 .\) Find these values of \(a\).

(b) Let \(n\) be a positive integer. For how many numbers \(a\) in \(\left\{2,3, \ldots, n^{2}-1\right\}\) is \(a^{2}-a\) divisible by \(n^{2} ?\) State your answer suitably in terms of \(n\) and justify.

## Solution

(a) We have \(10000=16 \times 625\) as product of prime powers. Recall the notation \(a \mid b,\) meaning \(b\) is divisible by a. We have \(10000 \mid a^{2}-a\) if and only if \((625 \mid a(a-1)\) and \(16 \mid a(a-1)) .\) Because \(a\) and \(a-1\) cannot share a factor, in turn this is equivalent to having both the conditions \((1) 625 \mid a\) or \(625 \mid a-1\) AND (2) \(16 \mid a\) or \(16 \mid a-1 .\) Now if the coprime integers 16 and 625 both divide the same natural number (in our case \(a\) or \(a-1),\) their product 10000 will also divide this number. In our case this would force \(a=0,1,\) or \(\geq 10000,\) all of which are not allowed. Thus the given requirement on \(a\) is equivalent to having either (1) \(16 \mid a\) and \(625 \mid a-1\) OR (2) \(16 \mid a-1\) and \(625 \mid\) a. Each case has a unique solution, respectively \(a=9376\) and \(a=625\) (e.g. use modular arithmetic: in case \(1,\) we have \(a=625 k+1,\) which is \(k+1\) mod \(16,\) forcing \(k=15\) because \(16 \mid a\) and \(a \in\{2,3, \ldots, 9999\})\)

(b) Let \(n=p_{1}{ }^{e_{1}} \ldots p_{k}{ }^{e_{k}}\) be the factorization of \(n\) into powers of distinct primes. The analysis in part (a) tells us that required values of \(a\) are obtained as follows: write \(n^{2}=x y\) as a product of two coprime integers and find values of \(a\) in \(\left\{2,3, \ldots, n^{2}-1\right\}\) that are simultaneously 0 mod \(x\) and 1 mod \(y\). These are precisely the values of \(a\) that we want. This is because each \(p_{i}^{2 e_{i}}\) must divide \(a\) or \(a-1,\) as \(a\) and \(a-1\) are coprime.

Now the Chinese remainder theorem tells us that there is always an \(a\) that is 0 mod \(x\) and 1 mod \(y\). It is also unique modulo \(x y=n^{2}\) because difference between any two solutions would be divisible by \(x y\).

The total number of ways to write \(n^{2}=x y\) as a product of coprime integers is exactly \(2^{k}\) as it amounts to choosing which of the \(k\) distinct primes to include in \(x\) and then the rest go into \(y\). (Notice that \(x\) and \(y\) are not interchangeable.) However, we have to delete the two cases \(x=1, y=n^{2}\) and \(y=1, x=n^{2},\) as these will respectively lead to solutions \(a=1\) and \(a=0\) or \(n^{2},\) which are not in \(\left\{2,3, \ldots, n^{2}-1\right\} .\) Finally it is easy to see that different choices of \(x\) lead to different values of \(a\). This is because, of the primes \(p_{1}, \ldots, p_{k}\) in the factorization of \(n,\) precisely the ones dividing \(x\) will divide \(a\) and the remaining primes will not, because they divide \(a-1\).

Thus the final answer is \(2^{k}-2 .\) Note that this matches with the special case in part (a). Finally, note that there was nothing special about taking a square: instead of \(n^{2}\) it could be any positive integer \(m\) and we would proceed the same way to find requisite integers \(a\) in \(\{2,3 \ldots, m-1\}\) based on prime factorization of \(m\)

### Primes in an algebraic equation ＊

B6, 2016

Find all pairs \((p, n)\) of positive integers where \(p\) is a prime number and \(p^{3}-p=n^{7}-n^{3}\)

## Solution

The given equation is \(p(p-1)(p+1)=n^{3}\left(n^{2}+1\right)(n+1)(n-1) .\) As the factor \(p\) on the LHS is a prime, it must divide one of the factors \(n-1, n, n+1, n^{2}+1\) on the RHS.

*Key lemma.* \(p>n^{2}\)

*Proof* The LHS \(=p^{3}-p\) is an increasing function of \(p\) for \(p \geq 1,\) e.g. because the derivative \(3 p^{2}-1\) is positive. So for any given \(n \geq 1\), there is exactly one real value of \(p\) for which LHS=RHS. Trying \(p=n^{2}\) gives LHS\(=n^{6}-n^{2}< n^{7}-n^{3}=\)RHS. This is because \(n^{7}-n^{3}-\left(n^{6}-n^{2}\right)=\left(n^{6}-n^{2}\right)(n-1)>0\). \(\,\square\)

As the prime \(p\) is greater than \(n^{2},\) it cannot divide any of \(n-1, n, n+1 .\) So \(p\) must divide \(n^{2}+1\) and therefore we must have \(p=n^{2}+1,\) again because \(p>n^{2} .\) Substituting this in the given equation, we get \(\left(n^{2}+1\right) n^{2}\left(n^{2}+2\right)=n^{3}\left(n^{2}+1\right)(n+1)(n-1)\). Canceling common factors gives \(n^{2}+2=n^{3}-n,\) i.e. \(2=n^{3}-n^{2}-n .\) This has a unique integer solution \(n=2,\) e.g. because the factor \(n\) on the RHS must divide 2 and now one checks that \(n=2\) works. So \(n=2\) and the prime \(p=n^{2}+1=5\) give a unique solution to the given equation.