A solution, including all the process that I got there with: Part 1: Experiments. Since I didn't see anything right away, I just looked for any $ m$ that worked with small values of $ n$. The results are here: $ \begin{array}{ccl}n&n^2-n+1&\text{Pairs}\\1&1&(2,1)\\2&3&(1,2),(2,2),(5,2)\\3&7& \\4&13& \\5&21&(2,5),(10,5)\\6&31& \\7&43& \\8&57& \\9&73& \\10&91&(5,10),(17,10)\end{array}$ Those pairs $ (5,2),(2,5)$ and $ (10,5),(5,10)$ looked suspicious. I tested $ (10,17)$; $ 17\cdot 10-1=13^2$ divides $ (289-17+1)^2=(13\cdot 21)^2$ Part 2: OK, we now have a plan. Conjecture: if $ (m,n)$ works, $ (n,m)$ does as well. Formally, we want to show that if $ mn-1$ divides $ (n^2-n+1)^2$, it also divides $ (m^2-m+1)^2$. We do some algebra mod $ mn-1$: $ 0\equiv (n^2-n+1)^2\equiv(n^2-n+1+mn-1)^2\equiv(n^2+mn-n)^2\equiv n^2(m+n-1)^2$ Since $ n$ is invertible mod $ mn-1$ (its inverse is $ m$), $ (m+n-1)^2\equiv 0\mod mn-1$. Similarly, $ (m^2-m+1)^2\equiv (m^2+mn-m)^2\equiv m^2(m+n-1)^2$; by the preceding, this is zero, and the conjecture is proved. Call it Lemma 1. I originally started by working with $ (m^2-m+1)^2-(n^2-n+1)^2$; that was dropped for clarity, after it led me to the above manipulation. Part 3: Now, we use Lemma 1 to build a ladder. In building the table, we notice that the solutions come in pairs at each $ n\ge 2$, corresponding to complementary divisors. Formalize this as Lemma 2: Lemma 2: If $ (m,n)$ is a solution, $ (m',n)$ is also a solution, where $ (n^2-n+1)^2=(mn-1)(m'n-1)$. Moreover, if $ n\ge 2$ and $ m<n$, $ m'\ge n$, and if $ n\ge 2$ and $ m>n$, $ m'\le n$. Proof of Lemma 2: By hypothesis, $ \frac{(n^2-n+1)^2}{mn-1}$ is a positive integer. Mod $ n$, this positive integer is $ \frac{1}{-1}\equiv -1$, and can be expressed as $ m'n-1$ for some $ m'>0$. If $ m<n$ and $ n\ge 2$, $ mn-1\le (n-1)n-1<n^2-n+1$ and thus $ m'n-1> n^2-n+1$, making $ m'\ge n$. If $ m> n$ and $ n\ge 2$, $ mn-1\ge n^2+n-1>n^2-n+1$ and thus $ m'n-1< n^2-n+1\le n^2-1$, making $ m'\le n$. By Lemma 2, if $ m>n$ and $ n\ge 2$, we can make a smaller solution with the same $ n$. By Lemma 1, if $ m<n$, we can make a solution with smaller $ n$. Any solution thus descends uniquely to a solution with $ n=1$ (which must be $ (2,1)$ by inspection), unless it hits a solution with $ m=n$ somewhere. We close that loophole with the next lemma. Lemma 3: The only solution of the form $ (n,n)$ is $ (2,2)$. Proof: Mod $ n^2-1$, $ (n^2-n+1)^2\equiv (-n+2)^2\equiv n^2-4n+4\equiv -4n+5$. In order to have $ n^2-1$ divide $ 4n-5$, we must have $ n^2-1\le 4n-5$, or equivalently $ n^2-4n+4=(n-2)^2\le 0$. That makes $ n=2$ the only possibility. It is easily confirmed to work. This argument fails where $ 4n-5<0$, but in that case $ n=1$ and $ 0$ does not divide $ 1$. Part 4: Enumerating the solutions. The solution $ (2,2)$ stands alone. We also have an infinite family of solutions of the form $ (a_{k-1},a_k)$ or $ (a_{k+1},a_k)$, where $ a_k$ is the infinite increasing sequence $ (1,2,5,10,17,\cdots)$. We would like to give a rule for this sequence. A little guesswork suggests that these are the squares plus 1; that should be easily testable. $ \left((k^2+1)^2-(k^2+1)+1\right)^2=(k^4+k^2+1)^2$ $ =(k^2+k+1)^2(k^2-k+1)^2$ $ (k^2+1)((k-1)^2+1)-1=(k^2+1)(k^2-2k+2)-1$ $ =k^4-2k^3+3k^2-2k+1=(k^2-k+1)^2$ $ (k^2+1)((k+1)^2+1)-1=(k^2+1)(k^2+2k+2)-1$ $ =k^4+2k^3+3k^2+2k+1=(k^2+k+1)^2$ They do work, so $ a_k=k^2+1$. Done.

MellowMelon wrote: Find all pairs of positive integers $ (m,n)$ such that $ mn - 1$ divides $ (n^2 - n + 1)^2$. Source unknown. I got an other solution but I also use Viete jump method . From the condition we have $ mn - 1|(n^2 - n + 1)^2$ and $ mn - 1|(m^2 - m + 1)^2$ , therefore $ (mn - 1)^2|[(n^2 - n + 1).(m^2 - m + 1)]^2$ or $ mn - 1|(m^2 - m + 1)(n^2 - n + 1)$ (*). Notice that $ mn\equiv 1 (\mod mn - 1)$ , from (*) we obtain the fact that :$ mn - 1|(m + n - 1)^2$ . Lemma : Let $ k = \frac {(m + n - 1)^2}{mn - 1}$ then $ k\in \{3,4\}$ . We will use Viete jump method here . Let $ (m_0,n_0)$ be the smallest positive integer root of this equation , we can assume that $ m_0\geq n_0$ . The equation can be rewritten in the form : \[ m^2 - m(kn + 2 - 2n) + (n - 1)^2 + k = 0\] This is quadratic equation of $ m$ so it has an other solution $ m_1$ . By the Viete law , we have $ m_o + m_1 = kn + 2 - 2n$ , notice that $ m_0$ is an integer so $ m_1$ is . We also have : $ m_1 = \frac {(n_0 - 1)^2 + k}{m_0}$ By the definition of $ m_0$ ,we obtain the fact that $ m_0\leq m_1 = \frac {(n_0 - 1)^2 + k}{m_o}$ . Expand this inequality ,we have : \[ k\geq (m_0 - n_0 + 1)(m_0 + n_0 - 1) (**)\] We have two case here : Case 1 : $ m_0 > n_0$ ,then we have $ k\geq 2(m_0 + n_0 - 1)$ . Replace it to (*) ,we have : \[ \frac {(m_0 + n_0 - 1)^2}{m_0\dot n_0 - 1}\geq 2(m_0 + n_0 - 1)\] This inequality is equivalent to the following inequality : \[ m_0 + n_0 - 1\geq m_0n_0 - 1 \leftrightarrow (m_0 - 1)(n_0 - 1)\leq 1\] Obvious this inequality holds iff $ (m_0,n_0) = (m_0,1)$ (pair $ (m_0,n_0) = (2,2)$ also satisfies condition ,but notice that we are considering $ m_0 > n_0$ ) . When $ n_0 = 1$ ,we have $ m_0 = 2$ and $ k = 4$ . That ends case 1 . Case 2 $ m_0 = n_0$ . From the condition we have $ m_0^2 - 1|(2m_0 - 1)^2$ , it is not very hard to show that only $ m_0 = 2$ satisfies this condition . When $ m_0 = n_0 = 2$ we have $ k = 3$ Thus ,lemma has been proven . We will solve equation for $ k = 3$ and $ k = 4$. For $ k = 4$ ,the equation can be rewritten in the form : \[ (m - n)^2 - 2(m + n) + 5 = 0\] Let $ m - n = 2t + 1$ then we have $ m + n = 2t^2 + 2t + 3$ .Solve this equation we have $ m = t^2 + 2t + 2$ and $ n = t^2 + 1$ . It is not hard to check that pair $ (m,n) = (t^2+2t+3 1,t^2+1) ,t\geq 1$ satisfies condition . For $ k = 3$ , the equation only has $ (m_0,n_0) = (2,2)$ as solution ,this equation can be solved by some inequality ...

You've got the answer wrong; both $ m$ and $ n$ should be quadratic in $ t$. The difference here: my method jumps from $ (a_k,a_{k-1})$ to $ (a_{k-1},a_k)$ and then to $ (a_{k+1},a_k)$, while yours goes from $ (a_k,a_{k-1})$ to $ (a_k,a_{k+1})$ and then to $ (a_{k+2},a_{k+1})$. You only get half of the solutions directly that way, so you need to do it twice. The bit "we can assume that $ m_0\ge n_0$" is false for your argument. It would probably have helped to actually write out the argument that you have everything.

jmerry, TTsphn's solution is correct. His $ m$ and $ n$ are indeed quadratic(Take a careful look at his $ m$ and $ n$). The only 'silly' mistake he made was assuming $ m-n = 2t+1$. Instead, he should have assumed $ m-n = 2t-1$. Then $ m + n = 2t^2 -2t +3$ which gives $ m= t^2 +1$ and $ n= (t-1)^2 + 1$. Then his solution also produces the same set of solutions.

TTsphn edited his post after I wrote that. It's right now, aside from the silly typo of "3 1" rather than "3-1". It does still only list half the solutions, and misses the base solution $ (2,1)$ as well.

A good solution , Tung , congratulation But i think , that problem is a easy problem ,The trick used to solve has become very familiar

de Vieta jump method will work on following problems : Problem 1: Let $ p;q$ be positive integers such that $ p\ge q$. Find all natural numbers $ a;b$ which satisfy $ \frac {(a - b)^2}{pab - q} = k (k\in \mathbb N)$ Problem 2: If there exists $ a;b \in \mathbb Z^{ + }$ satisfying $ \frac {(a - b)^2 + m}{pab - q} = k (m \in \mathbb N^*)$ with $ p;q$ are defined above then $ k$ (its value) belongs to a finite set.

MellowMelon wrote: Find all pairs of positive integers $ (m,n)$ such that $ mn - 1$ divides $ (n^2 - n + 1)^2$. Aaron Pixton. An old problem I had wirte condition $ mn - 1$ divides $ (n^2 - n + 1)^2$ equivalent $ mn-1$ divides $ (m-1)^2+(n-1)^2+1$ Put:$ a=x-1$,$ b=y-1$,we have :$ (ab+a+b)|(a^2+b^2+1$. Put:$ a^2+b^2+1=k(ab+a+b)$ (1) . Using Vieta jump method we have $ k=2$ When:(1) equivalent $ (a+b-1)^2=4ab$.(2) We have :$ gcd(a;b)=1$ so $ a=k^2;b=(k+1)^2$ If equation (2) be equation $ (a+b-5)^2=9ab$ then it is problem 2,USATST 2001,Day 3

A brief tutorial for my solution: Fully work and ignore the trivial solutions (namely $(2,2)$). Check the symmetry and ignore duplicated solutions. As you say $(m,n)$ is the solution with minimal $2< n < m$ you will try to find $k < n$ such that $(n,k)$ is also a solution. You need $(n^2-n+1)^2/N \equiv -1/1 \pmod n$ with $x\geq n^2-1$. Suppose that such $x$ doesn't exist. It yelds the chain of inequalities $$n^2-1 \leq \frac{(n^2-n+1)^2}{mn-1} \leq \frac{(n^2-n+1)^2}{n^2-1} \implies $$$$\frac{(n^2-n+1)^2}{n^2-1} \geq n^2-1 \iff n^2-n+1 \geq n^2-1 \iff n \leq 2$$and you obtained that all solutions are given by recurrences particular to a limited amount of solutions. More precisely Lemma 1. Fixing particulars $a_0$ and $b_0$ with $b_0 \leq 2$, all the solutions are given by, $$(a_i,b_i)_{i=0}^{\infty}\ |\ a_{i} = b_{i+1},\ b_{i} = \frac{1}{b_{i+1}}\left[ \frac{(b_{i+1}^2 - b_{i+1} + 1 )^2}{a_{i+1}b_{i+1}-1} +1 \right] \ \forall \ i \in \mathbb{N}^*.$$ Remark: You can go over the solutions you find with $a_0$ and $b_0$ satisfying $n \leq 2$. Working on Lemma 1 you find that the solutions are $(2,2)$ and $(m,n) = (b_{\ell-1},b_{\ell}), \ (b_{\ell},b_{\ell+1})\ \forall \ \ell \in \mathbb{N}^*$. Cleaning up Lemma 1 and adding the minimal solutions (notice that $(2,2)$ does not increase solutions in recurrence) $$b_{i+2} = \frac{b_{i+1}^3-2b_{i+1}^2+3b_{i+1}+b_{i}-2}{b_{i}b_{i+1}-1}\ \forall\ i \in \mathbb{N}^*,\ b_0 = 2,\ b_1 =5$$which yields the sequence $(b_i)_{i=0}^{\infty} = 2,5,10,17,\dots$ and it is not hard (or maybe not) to guess $$b_i = (i+1)^2+1$$and you are done as you proved that this contains all the solutions. $\blacksquare$

Hi, I'm reading TTsphn's Vieta Jump method, and I do not understand why $m-n=2n$ or why jmerry would say that it should be $2n-1$. Maybe there's a step in the solution that I overlooked, but to me, this implies that $m-n$ is odd, and where did that come from?

We can reduce this to $$mn -1 \mid (m+n-1)^{2}$$Now for this condition, we will vieta jump to get the minimal pair $(m,n)$ for some fixed value of $k$, where $$k = \frac{(m+n-1)^{2}}{mn -1}$$Now consider the pair with minimal $m+n$ which satisfies this, assume $m>n$, now vieta jump to get the other root $m'$, which will be $m' = (k-2)n + 2 - m = \frac{(n-1)^{2}+k}{m}$, note that $m' \geq m$, so we get that $$m^{2} - (n-1)^{2} \leq k = \frac{(m+n-1)^{2}}{mn -1}$$, now simplify to get that $$(m-n+1) \leq \frac{m+n -1}{mn -1} \leq \frac{2}{n}$$, simplify further to get that $$n(m-n+1) \leq 2$$, through this, we get that the minimal pairs that for some fixed value of $k$ are $(m,n) = (2,2),(2,1)$, so the values of $k$ are $3,4$, for $k=4$, the solutions are of the form $((t+1)^{2}+1,t^{2}+1)$ and for $k = 3$ the only solution that works is $(2,2)$, checking both is just a matter of algebra and vieta jumping, so we're done.

anurag27826 wrote: We can reduce this to $$mn -1 \mid (m+n-1)^[/u]{2}$$Now for this condition, we will vieta jump to get the minimal pair $(m,n)$ for some fixed value of $k$, where $$k = \frac{(m+n-1)^{2}}{mn -1}$$Now consider the pair with minimal $m+n$ which satisfies this, assume $m>n$, now vieta jump to get the other root $m'$, which will be $m' = (k-2)n + 2 - m = \frac{(n-1)^{2}+k}{m}$, note that $m' \geq m$, so we get that $$m^{2} - (n-1)^{2} \leq k = \frac{(m+n-1)^{2}}{mn -1}$$, now simplify to get that $$(m-n+1) \leq \frac{m+n -1}{mn -1} \leq \frac{2}{n}$$, simplify further to get that $$n(m-n+1) \leq 2$$, through this, we get that the minimal pairs that for some fixed value of $k$ are $(m,n) = (2,2),(2,1)$, so the values of $k$ are $3,4$, for $k=4$, the solutions are of the form $((t+1)^{2}+1,t^{2}+1)$ and for $k = 3$ the only solution that works is $(2,2)$, checking both is just a matter of algebra and vieta jumping, so we're done. how can we reduce this to mn-1|(m+n-1)^2 ?