For $n \ge 4$ find a factorization $n^2 - 3n + 1 = ab$ where $a \lt n$ and $b \lt n$.

Question

Update: We can use Willie Wong's argument to justify the definition of a 'truth cutoff' function,

$\quad \psi: \{3,4,5,6, \dots \} \to \{4,5,6,7, \dots \}$

For convenience we start with a preliminary definition,

$\quad \lambda(n,k) = n^2 -kn + 1$

To specify $\psi$:

For any $k \in \{3,5,6, \dots \}$ form the graph $C_k = \{\big(n, \lambda(n,k)\big) \mid n \ge k + 1\}$.

Find the smallest $N$ in the domain of $C_k$ such that for all $t \ge N$ the statement

$\quad [\lambda(t,k) = ab] \land [1 \lt a \lt t] \land [1 \lt b \lt t]$

is false.

Set $\psi(k) = N$.

Calculating,

$\; \psi(3) = 4$ and no predecessor to $4$.
$\; \psi(4) = 6$ and for the predecessor to $6$, $\lambda(5,4) = 6 = 2 \times 3$ with $2 \lt 5$ and $3 \lt 5$.
$\; \psi(5) = 9$ and for the predecessor to $9$, $\lambda(8,5) = 25 = 5 \times 5$ with $5 \lt 8$.
$\; \psi(6) = 12$ and for the predecessor to $12$, $\lambda(11,6) = 56 = 7 \times 8$ with $7 \lt 11$ and $8 \lt 11$.
$\; \psi(7) = 16$ and for the predecessor to $16$, $\lambda(15,7) = 121 = 11 \times 11$ with $11 \lt 15$.
$\; \psi(8) = 20$ and for the predecessor to $20$, $\lambda(19,8) = 210 = 14 \times 15$ with $14 \lt 19$ and $15 \lt 19$.
$\; \psi(9) = 25$ and for the predecessor to $25$, $\lambda(24,9) = 361 = 19 \times 19$ with $19 \lt 24$.
$\; \psi(10) = 30$ and for the predecessor to $30$, $\lambda(29,10) = 552 = 23 \times 24$ with $23 \lt 29$ and $24 \lt 29$.
$\; \psi(11) = 36$ and for the predecessor to $36$, $\lambda(35,11) = 841 = 29 \times 29$ with $29 \lt 35$.
$\; \psi(12) = 42$ and for the predecessor to $42$, $\lambda(41,12) = 1190 = 34 \times 35$ with $34 \lt 41$ and $35 \lt 41$.

and so on...

The patterns that $\psi$ exhibits are mildly interesting. I can predict that $\psi(13) = 49$ but not confident that I can put together a formal proof.

---

We are working with positive integers only.

Is there an example of positive integers $n \ge 4$, $a$ and $b$ with

$\tag 1 [n^2 - 3n + 1 = ab] \land [a \lt n] \land [b \lt n]$

Experimenting with Python I don't think the factorization is possible.

My work

I was working on finding the units in $\mathbb{Z}_{n}$ and if such factorizations are possible, then, well, back to the drawing board...

The goal is get the cutoff point for the 'upper segment' - find the largest $k$ with $3 \le k \lt n-1$ such that for $j \le k$

$\tag 2 [n^2 - jn + 1 = ab] \land [a \lt n] \land [b \lt n]$

is not possible.

So $\text{max } k$ is a function of $n$.

I gave an unorthodox answer to

Find the invertible elements and zero divisors in the ring $(\mathbb{Z}_{21}, +, \cdot)$. For each invertible element find the inverse.

and as k ranges $3$ to $11$ there are no factorizations and so knowing the maximum, $k = 11$, would cut down the amount of work and calculations.

See also this answer to finding the invertible elements in $(\mathbb{Z}_{12}, +, \cdot)$.

Answer 1

In terms of the question you asked:

$n^2 - 3n + 1 = (n-3)n + 1 > n(n-3)$. This means that if $ab = n^2 - 3n + 1$ and both $a < n$ and $b < n$, you can only have $\{a,b\} \subset \{n-1, n-2\}$, for if either is smaller than $n-2$ then $ab < n(n-3)$ by construction.

So you are asking whether there is an integer solution to one of the three equations

$$ n^2 - 3n + 1 = \begin{cases} n^2 - 2n + 1 \\ n^2 - 3n + 2 \\ n^2 - 4n + 4 \end{cases} $$

The first case is solved when $n = 0$, the second case has no solution, and the third when $n = 3$. Hence there are no other solutions with $n \geq 4$.