# Find all positve integers $n$ such that for all odd integers $a$, if $a^2 < n$ then $a | n$?

Find all positve integers $n$ such that for all odd integers $a$, if $a^2 < n$ then $a | n$ ? (Ref. Titu Andreescu, Number theory, page. 5-6).

OUTLINE OF THE AUTHOR'S SOLUTION:
Consider a fixed positive integer $n$. Let $a$ be the greatest odd integer such that $a^2 < n$ and hence $n \leq (a+2)^2$. If $a \geq 7$ then $a-4, a-2$ and $a$ are odd integers that divide $n$. Any two of these numbers are relatively prime so $(a-4)(a-2)a | n$. It follows that $(a-4)(a-2)a \leq (a+2)^2$ . Then $a^2 (a-7) + 4(a-1) \leq 0$ which is false.Thus $a$ is $1,3$ or $5$ . If $a=1$ then $1^2 \leq n \leq 3^2$ hence $n =\{1,2...,8\}$. Similarly for $a=3$ and $a=5$ . Thus $n = \{1,2,3,4,5,6,7,8,9,12,15,18,21,24,30,45\}$.

I HAVE THE FOLLOWING QUESTIONS IN RELATION TO THE SOLUTION GIVEN BY THE AUTHOR

1. Why does the author choose $a$ as the greatest odd integer ?
2. Why does the author use $\geq$ in the relation $a \geq 7$ and not other inequalities like $<$ etc. ?
3. How did the author arrive at the number $7$ in the relation $a \geq 7$ ?
4. How was the author able to choose $a-4, a-2$ and $a$ as the odd divisors of $n$ because if $a > 7$ then they are not the only odd divisors of $n$?

## 1. Why does the author choose $a$ as the greatest odd integer ?

Because the problem states "for all odd integers $a$, if $a^2 \lt n$". Since $a^2$ is bounded above by $n$, then $a$ must be bounded above by $\sqrt n$. So there must be a greatest odd integer $a$.

## 3. How did the author arrive at the number $7$ in the relation $a \geq 7$ ?

Probably, after working out some answers, with a computer or by hand, he hypothesized that $a$ must be less than 7. So he set about proving that $a \ge 7$ will not work.

Most authors do not explain how they came up with the numbers, formulas, equations, etc. that they used. They feel that their only obligation to the reader is to provide a valid proof and anything more is considered a distraction. Gauss and Ramanujen are famous for doing this.

## 4. How was the author able to choose $a-4, a-2$ and $a$ as the odd divisors of $n$ because if $a > 7$ then they are not the only odd divisors of $n$?

They aren't (necessarily) the odd divisors of $n$ but they are definitely odd divisors of $n$ given that $a \ge 7$.

There is a very subtle thing going on here. He states "any two of these numbers are relatively prime." What he is stating, without proof, is that any three consecutive odd numbers are pairwise prime. This is true and, because it is true, he can conclude that $(a-4)(a-2)a | n$. It turns out that any four consecutive odd numbers may not be pairwise prime; for example, $3,5,7,9$, where $\gcd(3,9) = 3$. This fact adds a bit of support to his use of the number $7$.

• Supposing $a\geq 5$. It is just large enough to get 3 the three largest consecutive odd numbers less than $n$, which sets up the cubic inequality, but then you can see by inspecting the inequality that it fails for $a\geq 7$.The motivation was to get a specific cubic inequality $p(a)\leq a$ with leading coefficient $1$ in $p$ .That puts an upper bound on $n$ – DanielWainfleet Nov 15 '15 at 17:12

1) Why does the author choose a to be the greatest odd integer?

Because if a wasn't the greatest, he couldn't say with certainty $(a + 2)^2 \ge n$, which is required for his proof. He knows that a greatest exists as n is finite.

2 & 3) Why does the author use $\ge$ than others. And why 7.

He wants to demonstrate something about the the three positive odd numbers a-4, a-2, and a. And it wouldn't work of a = 1. To have three positive odd numbers greater than 1, a must be at least 7.

4) How did the author arrive at a-4, a-3, a. If they aren't the only odd divisor?

They aren't the only but they are three. And being the largest three when he notes $a^2 (a-7) + 4(a-1) \leq 0$ this puts the greatest restriction on his results so he can conclude the most.