# Can we always find values $(a,d)$ such that $\frac{d+an}{4a-1}$ is an integer for all $n$

I'm working on determining if a certain form of simple hyperbolic diophantine equation always has solutions. I did some work and determined the answer is yes if the following fraction can always be an integer for some $a$ and some $d$ dividing $(an)^2$.

For all $n$, can we always find values $(a,d)$ such that $\dfrac{d+an}{4a-1}$ is an integer and where,

• $n$ is any fixed integer $\geq2$
• $a$ is any positive integer
• $d$ is a positive divisor of $(an)^2$.

Required: One need to find at least one couple $(a,d)$ per value of $n$ verifying the conditions.

I have checked for values of $n$ up to one million using a computer. Does anybody have any ideas how to show this is true or have a counterexample?

By the way, this purely recreational. Thanks for any help or ideas!

Edit: Sorry for the confusion. I only care that some $a$ and some $d$ dividing $(an)^2$ exist such that the fraction becomes an integer. But $a$ can take on any positive integer value.

Update: I have made some progress with the problem. I can show the statement holds for all integers not of the form $n=24k+1$. Furthermore, I can show that if the statement holds for a composite integer's prime factors, it holds for the composite number itself. So, I have narrowed the problem down to primes $n=p=24k+1$. Hopefully somebody has an idea to deal with the primes.

• So to be clear, $a$ is fixed and you search if there always exist $n,d$ satisfying this? – zwim Oct 23 '17 at 2:57
• No, this couldn't be that, else $n=d=(4a-1)$ is trivial solution. And this cannot be either for any $a,n,d$ since $a=1,n=d=5$ is a counter-example. Can you precise your request? Are you fixing $a,n$ and try to find $d$ ? – zwim Oct 23 '17 at 3:10
• Hello, everyone. Thanks for taking a look at the problem. First, let me address the update on my progress. It is a little lengthy to put into a single comment, so I will link to a pdf and just give the basic idea of the proofs. The pdf of my progress can be found here: drive.google.com/file/d/1Vi-RuPzYSSOU6JYij7s4zZm-byEtUMKL/… . First, getting to $n = 12k + 1$: When $n = 6k + 1$, take $k = 2l + 1$ and $n \equiv 3 (mod 4)$ and we can find $a$ such that $n = 4a-1$. Use that $a$ and take $d = n$ to show the fraction is an integer. – Greg Nov 28 '17 at 5:04
• Second, getting to $n = 24k + 1$: Notice that $an = 4a3k + a \equiv 3k + a (\mod 4a-1)$. If $an \equiv 3a - 1 (\mod 4a-1)$ we can choose $d = a$ and have $d + an \equiv 0 (\mod 4a-1)$. Solving when $a + 3k = 3a - 1$, we get $a = \frac{3k+1}{2}$ which is an integer when $k$ is odd. So, when $k$ is odd, we can find values of $a, d$ where the fraction Is an integer. – Greg Nov 28 '17 at 5:18
• Lastly, addressing composite numbers, we can take any composite number which has a prime $p$ such that $\frac{d_p + a_p p}{4a_p-1}$ is an integer. You can then choose $d = \frac{nd_p}{p}$ and $a = a_p$ to see that $\frac{d + an}{4a-1}$ is an integer. Note that $d = \frac{nd_p}{p} | (a_pn)^2 = (an)^2$. I left some detail out, but that is the idea I used. See my pdf for a more detailed explanation. – Greg Nov 28 '17 at 5:26

This answer deals with the case for $n=6k+1$ since zwim has already dealt with the cases for $n=6k+r$ where $r$ is either $0,2,3,4$ or $5$.

I think some results you've written in "Update" are important, so let me add my proof for them here.

I can show the statement holds for all integers not of the form $n=24k+1$.

Proof :

If $n=24k+7$, then since $n\equiv -1\pmod 4$, there is at least one prime $p$ of the form $4s-1$ such that $p\mid n$, so $\frac{d+an}{4a-1}$ is an integer for $(a,d)=(s,n)$ as follows :$$\frac{d+an}{4a-1}=\frac{n+sn}{4s-1}=\frac{n(s+1)}{4s-1}=(s+1)\times (\text{an integer})$$

If $n=24k+13$, then since $n+1=2(12k+7)$ with $12k+7\equiv -1\pmod 4$, there is at least one prime $p$ of the form $4s-1$ such that $p\mid 12k+7$, so $\frac{d+an}{4a-1}$ is an integer for $(a,d)=(s,sn^2)$ as follows : $$\frac{d+an}{4a-1}=\frac{sn^2+sn}{4s-1}=\frac{sn(n+1)}{4s-1}=2sn\times (\text{an integer})$$

If $n=24k+19$, then we can find $(a,d)$ in the similar way as the case where $n=24k+7$. $\quad\blacksquare$

I can show that if the statement holds for a composite integer's prime factors, it holds for the composite number itself.

Proof : Let $n=pq$. If there is a pair of positive integers $(a_1,d_1)$ such that $\frac{d_1+a_1p}{4a_1-1}$ is an integer with $d_1\mid (a_1p)^2$, then $\frac{d+an}{4a-1}$ is an integer for $(a,d)=(a_1,d_1q)$ satisfying $d\mid (an)^2$. $\quad\blacksquare$

Next, let us show some partial results for primes $n=24k+1$. (Michael's comments are helpful here.)

• If $n=24k+1$ whose right-most digit is $3$ in decimal representation ($n$ is not necessarily prime), then solving $24k+1\equiv 3\pmod{10}$, we see that there is an integer $m$ such that $k=5m+3$, and that $\frac{d+an}{4a-1}$ is an integer for $(a,d)=(4,8)$ as follows : $$\frac{d+an}{4a-1}=\frac{8+4(24(5m+3)+1)}{4\cdot 4-1}=32m+20$$

• If $n=24k+1$ whose right-most digit is $7$ in decimal representation ($n$ is not necessarily prime), then solving $24k+1\equiv 7\pmod{10}$, we see that that there is an integer $m$ such that $k=5m+4$, and that $\frac{d+an}{4a-1}$ is an integer for $(a,d)=(4,2)$ as follows : $$\frac{d+an}{4a-1}=\frac{2+4(24(5m+4)+1)}{4\cdot 4-1}=32m+26$$

• If $n=24k+1$ is prime, then we may suppose that $d$ is either $1,a,a^2,a',a'n$ or $a'n^2$ where $a'\ (\not=1,a,a^2)$ is a divisor of $a^2$ because of the followings where we use that $\gcd(2an,4a-1)=1$ : \begin{align}&\text{If d=1 or d=a^2n^2, then \frac{d+an}{4a-1}\in\mathbb Z if and only if \frac{an+1}{4a-1}\in\mathbb Z}\\\\& \text{If d=a or d=an^2, then \frac{d+an}{4a-1}\in\mathbb Z if and only if \frac{12k+1}{4a-1}\in\mathbb Z}\\\\& \text{If d=a^2 or d=n^2, then \frac{d+an}{4a-1}\in\mathbb Z if and only if \frac{a+n}{4a-1}\in\mathbb Z}\\\\&\text{If d=n or d=a^2n, then \frac{d+an}{4a-1}\in\mathbb Z if and only if \frac{a+1}{4a-1}\in\mathbb Z which cannot be an integer}\\\\& \text{If d=an, then \frac{d+an}{4a-1}=\frac{2an}{4a-1} cannot be an integer}\end{align}

• If $n=24k+1$ is prime and $12k+1$ has at least one prime factor of the form $4s-1$, then $\frac{d+an}{4a-1}$ is an integer for $(a,d)=(s,s)$ as follows : $$\frac{d+an}{4a-1}=\frac{2s(12k+1)}{4s-1}=2s\times (\text{an integer})$$

So, the remaining cases are primes of the form $n=24k+1$ such that

• The right-most digit in decimal representation is either $1$ or $9$

• $12k+1$ has no prime factors of the form $4s-1$

• Thanks for the excellent answer! Your solution for those numbers congruent to 3 mod 10 and 7 mod 10 makes me wonder if something similar is possible for those ending in 1 or 9. – Greg Nov 28 '17 at 7:30
• I tried the $a'n$ and $a'n^2$ ideas, update in my post, but still there are some blocking issues. – zwim Nov 28 '17 at 15:17

I have a partial result.

For $n=3q+r$ with $r\in\{0,1,2\}$

We have for $a=1$ $$F=\dfrac{an+d}{4a-1}=\dfrac{3q+r+d}3=q+\dfrac{d+r}3$$

• For $r=0$ then $d=3\qquad$ [ $n^2=(3q)^2$ so $d\mid n^2$ ]

• For $r=2$ then $d=1\qquad$ [ $d=1$ always divides $n^2$ ]

• For $r=1$ then $d=2$ and $q\text{ odd}\qquad$ [ $n^2\equiv q+1\pmod{2}$, so if $q$ odd $d=2$ divides $n^2$ ]

In all three cases then $d+r=3$ so $F$ is an integer.

The only difficult case appears to be when $n=6p+1$.

For that case, the simulation on computer does not show a good pattern for $a$ or $d$.

### Edit 28/11

Inspired by mathlove post I took my chance at endings $1,9$ in decimal or or $k=5m,5m+2$.

The most promising road was $\begin{cases}a=uv\\d=un\end{cases}$

Resulting in $\dfrac{u(1+v)}{4uv−1}\in\mathbb N$.

Unfortunately the numerator is too small and this doesn't work out.

Then I explorer another idea with computer simulation $\begin{cases}a=uv\\d=uan^2\end{cases}$

In this case $f(a,d,n)=\dfrac{an+d}{4a-1}=an\times\dfrac{1+un}{4uv-1}=an\times g(u,v,n)$.

Still for the $n=24k+1$ primes, this reduced problem $g(u,v,n)\in\mathbb N$ seems almost always to have a solution in $(u,v)$

Only very few cases actually do not work (either impossible or u,v were possibly too large).

$k\in\{8,105,2772,3185,10500,13217,13728,16875,50547,59892,72140,81593,83252,...\}$

I don't know what particularity these numbers share, maybe it is a good place to dig in, or maybe it also means that we have to go for another approach. Anyway, if anyone is tempted to explore further, this is what to expect.

• Thanks for the partial solution. Indeed, the n=6k+1 is the troublesome case. – Greg Oct 24 '17 at 10:11
• Looking at my data last night, I noticed that only the primes are requiring larger values of $a$. For composite numbers up to $n=25000$ the value of $a$ was almost always 1,2,3, or 4. I found 3 occurrences of $a=6$ (no 5's), so I don't have a very good reason to believe that 6 should be the max. I will automate my check after work today to see if any larger values of $a$ than 6 occur for composite numbers up to one million. As a note, the times when $a=6$ occurred were when $n$ had a factor of 79, the first being $79^2$. – Greg Oct 24 '17 at 22:39
• There are many primes with high values for $a$, and when you multiply such two you also often end up with a case where $a$ is big for the composite number: cjoint.com/c/GJyxMd6ut2N So the method of studying for small $a$ is not very promising. Instead, one has to find $a=f(n)$ which could lead to simplifications. Anyway, I have no idea to go further at the moment, hope someone new gets interested in the problem. – zwim Oct 24 '17 at 23:39
• I figured that would be the case, but hadn't had the chance to verify. The values for $a$ seem very erratic, as you mentioned already. So, finding such a function will be very difficult. I'll keep digging, though. – Greg Oct 25 '17 at 0:00
• The "certain form of a simple hyperbolic Diophantine equation" wouldn't happen to be $4/n = 1/a + 1/b + 1/c$, would it? – Craig Nov 27 '17 at 19:24