Consecutive integers divisible by prime powers

elementary-number-theorymodular arithmeticnumber theory

There's a similar question on here already but I don't think the answers are applicable in this case.

Question: Find the smallest three consecutive integers for which the first integer is divisible by the square of a prime; the second integer by the cube of a prime; and the third integer by the fourth power of a prime.

My attempt: Let the three consecutive integers be a, b and c. Then

$a\equiv 0\pmod{d^2}$

$a+1\equiv 0\pmod{e^3}$

$a+2\equiv 0\pmod{f^4}$

where $d,e,f$ are prime. This is equivalent to

$a\equiv 0\pmod{d^2}$

$a\equiv -1\pmod{e^3}$

$a\equiv -2\pmod{f^4}$

Then after applying the Chinese Remainder Theorem,

$e^3f^4a\equiv 1\pmod{d^2}$

$d^2f^4a\equiv 1\pmod{e^3}$

$d^2e^3a\equiv 1\pmod{f^4}$

I don't think this is getting me anywhere. Is this sort of general approach going to work or am I wasting my time?

Best Answer

Hint: It's a good idea to think about which primes these primes could be. For example, since you're looking for small numbers, you probably want to see what happens if you stipulate that the prime $p$ so $p^4$ divides your largest number is $2$ -- then try for $3$, $5$, etc. until you find that your result ends up being too big. I'll show you a worked example for the simpler problem of finding two consecutive numbers the first of which has a perfect square of a prime as a factor and the second of which has the perfect cube of a prime as a factor:

Let our integers be $a$ and $a+1$. We know that either $8|a+1$ (so $2$ is our prime) or $a+1\geq 27$. Let's first try the case $8|a+1$. Then we want to find a number that the perfect square of a prime divides in the sequence

$$7, 15, 23, 31, 39, 47, 55, 63, 71...$$

and we find that the first one occurs at $63$, so ($63,64$) is a solution. Now let's try when $27|a+1$. We get that $a$ is in

$$26, 53, 80...$$

and then everything above $53$ is too big, since we've already found the example $(63,64)$. Now, if our prime is any bigger than $3$, we get that $a+1\geq 125$, which is going to give us something much larger than $(63,64)$, and thus $(63,64)$ is our answer.

Related Question