# Existence of divisor of multiple of primes congruent to 1 mod 4

Show that for every prime $$p\equiv 1\pmod 4$$, there exists positive integers, $$n,m$$ such that

$$n(4m-p)-1\mid mp$$

Or equivalent, if we let $$m= \frac{p+4k+3}{4}$$,

$$n(4k+3)-1\mid p\left(\frac{p+4k+3}{4}\right)$$

Often we can find solutions to

$$n(4k+3)-1= p$$

but this isn’t always true. For example, there are no such solutions for $$p=73$$. Instead we can pick $$n=3$$, $$k=1$$, to get $$20\mid 73\cdot 20$$

Update: on further investigation this is simply a potential special case solution of the Erdos-Strauss conjecture since $$l(m(4n-p)-1)=mp$$ can be arranged to $$\frac{4}{p} = \frac{1}{mnp}+\frac{1}{n}+\frac{1}{ln}$$.

We solve the problem in the following way:

Proposition. Let $$p\equiv 1\pmod 4$$, then there exists positive integers $$m,n$$ such that $$n(4m-p)-1 \mid m$$

Hence $$n(4m-p)-1$$ will also divide $$mp$$. This does not depend on $$p$$ being prime.

Proof. If $$p=3$$, we let $$(m,n)=(1,2)$$ so that $$n(4m-p)-1 = 2(4-3)-1 = 1$$

Otherwise, we may assume $$p\equiv 1,2\pmod 3$$. Since $$p\equiv 1\pmod 4$$, this means $$p\equiv 1,5 \pmod{12}$$.

# Case 1: $$p\equiv 1 \pmod {12}$$

We split this into two cases instead: $$p\equiv 1,13\pmod{24}$$. First let $$p=1+24r$$. We set $$(m,n)=(6r,1)$$, so that $$n(4m-p)-1 = (24r-(1+24r))-1 = -2$$ which divides $$m=6r$$.

For the second case of $$p=13+24r$$, we set $$(m,n)=(6r+4,1)$$, giving $$n(4m-p)-1 = (24r+16-(13+24r))-1 = 2$$ which also divides $$m=2(3r+2)$$.

# Case 2: $$p \equiv 5 \pmod {12}$$.

Similarly we split this into two cases, $$p\equiv 5,17 \pmod{24}$$. For $$p=5+24r$$, we set $$(m,n) = (6r+2,1)$$. This gives $$n(4m-p)-1 = (24r+8-(5+24r))-1 = 2$$ which divides $$m=2(3r+1)$$.

For the other case of $$p=17+24r$$, we use $$(m,n) = (6r+4,1)$$ to get $$n(4m-p)-1 = (24r+16-(17+24r))-1=-2,$$ which also divides $$m=2(3r+2)$$.

$$\tag*{\square}$$

# Extras.

It seems trickier to require $$n(4m-p)-1=dp$$ for some positive integer $$d$$ instead. In particular, it is related to another unanswered problem. (The relationship being this is a sub-problem of that, which has a more general $$p$$ instead of prime.)

For the case of $$p\equiv 5 \pmod 8$$, there is a straightforward answer.

# Case 1: $$p\equiv 5 \pmod 8$$

The approach is to set $$n(4m-p)-1=p$$.
Let $$p\equiv 5 \pmod 8$$ and write $$p=5+8r$$. Choose $$n=2$$ and set $$m=\frac{1}{4}\left(\frac{p+1}{n}+p \right)$$ Then $$\frac{p+1}{n} = \frac{6+8r}{2} = 3+4r\equiv 3 \pmod 4$$ Since $$p\equiv 1 \pmod 4$$, $$m$$ is an integer.

Now we observe that $$n(4m-p)-1 = n\left(\frac{p+1}{n}+p - p\right)-1= (p+1)-1=p$$ Therefore $$n(4m-p)-1 = p \mid mp$$

# Case 2: $$p\equiv 1 \pmod 8$$

The previous method cannot still work because $$m$$ is not integral for $$p\equiv 1 \pmod 8$$.

# Connection to another problem

The other problem is as follows:

Let $$5< p=a^2+b^2$$ be odd and squarefree. Show that there exists positive integers $$1\leq m$$ and $$7 \leq k\equiv 3\pmod 4$$ such that $$X^2-mkX+m\frac{(kp+1)}{4} = 0$$ has integer roots.

Suppose we can always find a solution of the form $$n(4m-p)-1 = dp \mid mp$$ for some positive integers $$(m,n,d)$$. Then $$d$$ divides $$m$$, so we may replace $$m$$ with $$dm$$. i.e. solving $$n(4dm-p)-1 = dp \mid (dm)p$$ Let $$n=k-d$$ and $$w=k-2d$$, then this becomes \begin{align*} n(4md-p)-1 &= dp\\ (k-d)(4md-p) &= dp+1\\ 4md(k-d) &= kp+1\\ m(2d)(2k-2d) &= kp+1\\ m(k-w)(k+w) &= kp+1\\ mk^2-kp-1 &= mw^2\\ m^2k^2-mkp-m &= (mw)^2 \end{align*} Now since $$m^2k^2-mkp-m$$ is the discriminant $$D$$ of the equation $$X^2-mkX+m\frac{kq+1}{4}=0$$ This shows that the equation has solutions $$\frac{mk\pm \sqrt{D}}{2} = \frac{mk \pm mw}{2}$$ which must be integral (either $$m$$ even or $$k$$ and $$w$$ can be shown to be odd).

We also require $$k\equiv 3\pmod 4$$, which can be shown as follows: \begin{align*} n(4m-p)-1 &= dp\\ (k-d)(4m-p)-1 &= dp\\ (k-d)(-1)-1 &\equiv d \pmod 4\\ d-k-1 &\equiv d \pmod 4\\ k &\equiv 3 \pmod 4 \end{align*} Since $$k=n+d$$ it is always positive, but there is a small problem that it might be equal to $$3$$.