Find a positive integer $n$,$m$, $p$, $q$ ($p \neq q$, $m>1$) such that $p$ and $q$ divide $mn^2 - 1$ and $mn$ divides $p - q$.

Question

Our programming teacher asked us to find triple positive integers n,p,q (m=2) such that:

$p$ and $q$ divide $2n² - 1$ and $2n$ divides $p - q$

With the program below, I didn't find such an integer (I stopped the iterations at 1000000). So, I wonder if such an integer n does exist or if my program is faulty.

        from sympy import isprime
def find_integers():
    solutions = []
    max_n = 10**6  # Upper limit for n
    for n in range(1, max_n + 1):
        if not isprime(2 * n ** 2 - 1):
        for p in range(1, 2 * n ** 2 - 1, 2):
            for q in range(1, 2 * n ** 2 - 1, 2):
                if (2 * n ** 2 - 1) % p == 0 and (2 * n ** 2 - 1) % q == 0 and (p - q) % (2 * n) == 0 and p != q:
                    solutions.append((n, p, q))
            if n % 100 == 0:  # Print progress every 100 iterations
                print(f"Progress: n = {n}")
    return solutions
# Find the solutions
solutions = find_integers()
# Display the results
if solutions:
    print("Solutions:")
    for i, (n, p, q) in enumerate(solutions):
        print(f"Solution {i + 1}: n = {n}, p = {p}, q = {q}")
else:
    print("No solutions found.")

Addition: This question is completely resolved: In the case m=2 by Denis Shatrov in this thread and in the case m>1 by GH from MO in MO

Answer 1

There is no integers $n$, $p \ne q$ such that $p, q \mid 2n^2 - 1$, $p, q > 0$, $p \equiv q \pmod{2n}$. The following solution is based on the theory of generalized Pell's equation.

If $\gcd(p, q) > 1$, then $p', q' \mid 2n^2 - 1$ and $p' \equiv q' \pmod{2n}$, where $p' = \frac{p}{\gcd(p, q)}$, $q' = \frac{q}{\gcd(p, q)}$. Hence, $p$ and $q$ can be considered coprime. Hence, $pq \mid 2n^2 - 1$. Let $q = p + 2nt$. We get the equation

$$2n^2 - 1 = sp(p + 2nt)$$ $$(2n - spt)^2 - (s^2t^2 + 2s)p^2 = 2$$ This is a generalized Pell's equation. Associated Pell's equation is $$x^2 - (s^2t^2 + 2s)y^2 = 1$$ which has fundamental solution $(st^2 + 1, t)$. Solutions of the generalized Pell's equation can be bounded. See https://en.m.wikipedia.org/wiki/Pell%27s_equation, section "Generalized Pell's equation".

$$p \le \sqrt{2} \frac{\sqrt{st^2 + 1 + t\sqrt{s^2t^2 + 2s} } + 1}{2 \sqrt{s^2t^2 + 2s}} < 2$$ Hence, $p \in \{0, 1\}$. Case $p = 0$ is clearly impossible. Case $p = 1$ is impossible, because for $t > 1$ we have $(st)^2 < s^2t^2 + 2s + 2 < (st + 1)^2$. Case $t = 1$ gives equation $$(2n - sp)^2 = s^2 + 2s + 2$$ which has no solutions.

Answer 2

Is there an integer $n$ such that $2n^2-1$ has two distinct positive divisors congruent modulo $2n$?

We prove that the answer to this question is "NO".

Suppose such an integer $n$ exists: $\exists p, t \in \mathbb{N}^*$ such that $p$ and $p+2tn$ are divisors of $2n^2-1$. Let $d = p \wedge (p+2tn)$. We have: $2n^2-1 \equiv 0 \pmod{d}$, $d \wedge 2n = 1$, $d$ divides $2tn$, $d$ divides $t$. By dividing $p$ and $p+2tn$ by $d$, we obtain two divisors of $2n^2-1$ that are coprime and congruent modulo $2n$. $\exists p, t, q \in \mathbb{N}^*$ such that $2n^2-1=pq(p+2tn)$. Denoting $X=q(p+tn)$, $Y=n$, $A=q(qt^2+2)$, this can be written as: $X^2-AY^2=-q$. (*)

Let $\alpha = \sqrt{A}$. It is not very difficult to ensure that $\alpha \notin \mathbb{Q}$. (Otherwise $\exists u \in \mathbb{N}^*$ such that $(qt^2+1)^2=(ut)^2+1$.)

Case where $t \geq 2$.

From (*), we deduce that $|X-\alpha Y|=\dfrac q{|X+\alpha Y|}<\dfrac q{\alpha Y}< \dfrac 1{tY}\leqslant \dfrac 1{2Y}$. This inequality implies that $\frac XY$ is a "reduced" form of $\alpha$.

We will use the following result, valid for any $\alpha$, non-integer square root of an integer. Let $(\alpha_n)_{n\in \mathbb{N}}$ be the sequence defined by $\alpha_0=\alpha$, $\forall n \in \mathbb{N}, \alpha_{n+1} = \frac{1}{\alpha_n} - \lfloor \alpha_n \rfloor$. Then, $\forall n \in \mathbb{N}$, $\exists a_n, b_n \in \mathbb{N}$ such that $\alpha_n = a_n + \alpha b_n$ and for any reduced form $XY$ of $\alpha$, $\exists n \in \mathbb{N}$ such that $|X^2-AY^2| = b_n$.

It follows that $\forall t \geq 2$, $|X^2-AY^2| \in \{b_n | n \in \mathbb{N}\}$. Now the sequences $(\alpha_n)$ and $(b_n)$ are periodic: $\lfloor \alpha \rfloor = qt$.

$\alpha_0=\alpha$, $\alpha_1=qt+\alpha2q$, $\alpha_2=qt+\alpha$, $\alpha_3=qt+\alpha2q$, $b_0=1$, $b_1=2q$, $b_2=1$, $b_3=2q$. $|X^2-AY^2| \in \{1, 2q\}$ contradicts (*).

Case where $t=1$.

With $x=p+n$ and $y=n$, $2n^2-1=pq(p+n)$ becomes: $qx^2-(q+2)y^2=-1$. () So, by Bezout's equation, $\exists k \in \mathbb{N}$ such that: $\begin{cases} x^2=q+\frac{3}{2}+k(q+2) \\ y^2=q+\frac{1}{2}+kq \end{cases}$. We have: $k \neq 0$. (Otherwise $x^2-y^2=1$ forces $y=0$ and a contradiction). Thus, any solution $(x,y)$ in $\mathbb{N}^2$ of () satisfies $x > \sqrt{3q}$. $(qx,y)$ is then a solution of the Diophantine equation $X^2-q(q+2)Y^2=-q$. We will prove that this equation has no solution.

Let $H$ be the branch of hyperbola $H=\{(X,Y) \in \mathbb{R} \times \mathbb{R}^+ | X^2-q(q+2)Y^2=-q\}$, $A(0,\frac{1}{\sqrt{q+2}}) \in H$, $H=H \cap \mathbb{Z}^2$, $\Phi$ the element of $L(\mathbb{R}^2)$ whose matrix in the canonical basis is $M=(q+1)^{-1} \begin{pmatrix} q+1 & q \\ 1 & 1 \end{pmatrix}$.

Then $\Phi$ permutes the elements of $H$ and $H$. So $\Phi(A) \in H$. Finally, let $\Delta$ be the arc of $H$ with endpoints $A$ and $\Phi(A)$.

$\forall (X,Y) \in H$, $\exists n \in \mathbb{Z}$, $\exists (X_0,Y_0) \in \Delta \cap \mathbb{Z}^2$ such that $(X,Y) = \Phi^n(X_0,Y_0)$. This means that $\Delta \cap \mathbb{Z}^2$ is a "fundamental domain for the action of the group generated by $\Phi$ on $H$," i.e., if $H \neq \emptyset$, $H$ is partitioned into a finite number of orbits under this action, each having a unique representative in $\Delta \cap \mathbb{Z}^2$.

But the abscissa of $\Phi(A)$ is $\sqrt{q}$. $\Delta = \{(X,Y) \in H | 0 \leq X \leq \sqrt{q}\} = \{(qx,y) \in H | 0 \leq x \leq \sqrt{q+2}\}$.

For $q>2$, the inequality $x \leq \sqrt{q+2}$ contradicts (**). So: $\Delta \cap \mathbb{Z}^2 = \emptyset$. $H = \emptyset$. $\square$