cosinerburc wrote: Find in explicit form all ordered pairs of positive integers $(m, n)$ such that $mn-1$ divides $m^2 + n^2$. This problem is es exactly to another one, but I could not find it, but I remember tha if $a,\, b$ and $\frac{a^2+b^2}{ab-1}=q$ are integers then $q=5$ so, in this case $m^2+n^2=5mn-5$ and how you can see in the other Topic the solution is $(2,1)$. Best Regards. RX the Crazy Math

i know that q is 5,i mean i read it in a book,also the solution after realising that q=5; but do u know how i can find that q=5

RobertuX wrote: if $a,\, b$ and $\frac{a^2+b^2}{ab-1}=q$ are integers then $q=5$ I tried to prove it but I failed Can you give your proof?

I think stuff like this has been proven before on the forum. In fact, I think I can recall Myth solving this very problem. Try an infinite descent approach. I don't have the time to work out the details, but try to find, from a solution $(a_n,b_n)$ with $a\le b$, a solution $(a_{n+1},b_{n+1})$ with $a_{n+1}\le b_{n+1}$ and $b_{n+1}=a_n$. You have to solve a second degree equation in order to do this.

cosinerburc wrote: i know that q is 5,i mean i read it in a book,also the solution after realising that q=5; but do u know how i can find that q=5 I think will be a good idea to find the another TOPIC, I couldn't find, so maybe Groober knows, ask him and in the topic you can find the solution of the problem. Best Regards RX The Crazy Math

Here goes the solution. The infinit descent grobber was talking about is to show that if $(a,b)$ is a solution with $a\leq b$ then $a,ka-b$ is also a solution and is a smaller one (that is, $(x,y)$ is smaller than $(u,v)$ iff $x<y$ or $x=y$ and $u<v$). Just check to see that indeed $(a,ka-b)$ is a solution. We still have to prove that $ka-b>0$ and to prove that this solution is smaller, we have to show $ka-b<b$. So, let's write the quadratic. $a^2-a(kb)+b^2+k=0$. Let $c$ be the other solution, different from $a$ of this quadratic. Then we have $a+c=kb, ac=b^2+k$. Now, if $k\leq\frac ba\Rightarrow a+c\leq \frac {b^2}a\Rightarrow a^2+b^2+k\leq b^2$, false. $\frac {a^2+b^2}{ab-1}>\frac {2b}a\Leftrightarrow 2b>a(b^2-a^2) (1)$. But $a=b$ gives no solution, so $a^2\leq (b-1)^2$. So putting this upper, we have $a(b^2-a^2)\geq a(2b-1)\geq 2(2b-1)>2b$, if $a\geq 2$, so we can't have $(1)$. If $a=1$, we must have $b=2$ to have (1) true. So, unless we have reached the minimal solution $(1,2)$, we can find a smaller solution from $(a,b)$, so go lower 'till we must reach the $(a,2)$ pair at some point. Because $k$ remains unchanged, it follows that $k=5$ for every such a pair.

one more thing I know I left the problem unfinished, but it's really hard to determine all the solutions and probably it would cost a lot of extrawork because, when trying to go reverse you can obtain 2 different bigger solutions from a given solution. For example, from $(1,2)$ you can obtain $(1,5\cdot 1-3)$ and $(2,5\cdot 2-1)$. i don't know how all these solutions can be generated.

$(1,5\cdot 1-3)=(1,2)$..

Something wrong in ikap's last statement. Solutions can be generated in the unique way.

oops, right so $5a_n-b_n=a_{n-1} \&\& a_n=b_{n-1}$. This is a recurence formula only starting from pairs $(2,9)$ and $3,14$. From here we can prove that $4a_n\leq b_n\Leftrightarrow 4b_{n-1}\leq 5b_{n-1}-a_{n-1}$, and from this it follows that the other pair $(a_{n+1},b_{n+1})$ than the one described upper is in fact smaller than $(a_n,b_n)$ so it can't be. Solving the above recurence and adding tot those solutions $(1,2), (1,3)$ gives us all the solutions.

ikap wrote: $\frac {a^2+b^2}{ab-1}<\frac {2b}a\Leftrightarrow 2b>a(b^2-a^2) (1)$ Well this is NOT ok, you need to do better your calculus because $> \to <$ in the 2nd expression. Sorry and best regards. RX the Crazy Math

Yes, Robertux, but if u would have followed the line of my proof you would have noticed that what I needed to show was that $k\leq \frac {2b}a$, so I supposed $k> \frac{2b}a$ so only the first sign should be inverted in what you have quoted. If you don't understand the solution don't hesitate to ask. And, something more. Calculus is something completely different from computation.

ikap wrote: And, something more. Calculus is something completely different from computation. WoW, I see a philosophical underlying theme here.

Myth wrote: ikap wrote: And, something more. Calculus is something completely different from computation. WoW, I see a philosophical underlying theme here. It goes far beyond my power of understanding . Maybe a hint to make me understand where the philosophy is

ikap wrote: Myth wrote: ikap wrote: And, something more. Calculus is something completely different from computation. WoW, I see a philosophical underlying theme here. It goes far beyond my power of understanding . Maybe a hint to make me understand where the philosophy is mmmm, anyway if you don't understand your mistakes, is not my problem (I assume that $a b-1 \ge 0$).

I've already told you which was the one and only mistake, and now it's fixed. It would be another mistake there $5\cdot 1-3\neq 2$ but that one remains for posterity.

ikap wrote: I've already told you which was the one and only mistake, and now it's fixed. It would be another mistake there $5\cdot 1-3\neq 2$ but that one remains for posterity. Well. move this TOPIC to solved topics, I only know that was a simple problem and I am ready to "try" new problems, I suppose that the idea in the forum is to know new ways to solve problems, and not only solve the problems. So, I hope people learn math and technics to solve it. As you know, I am teacher in the university and this is one of my interest in science. Best regards. RX the Crazy Math

ok, ok, sorry, be sure to have all my respect, i didn't wanted to irritate you, just wanted to make it clear.

BTW, as grobber said, this problem really appeared three times on forum. And I wrote a solution for it some weeks ago...

ikap wrote: ok, ok, sorry, be sure to have all my respect, i didn't wanted to irritate you, just wanted to make it clear. I never was irritate, don't worry about that, I only want to help another guys learn.

About the problem, see also http://www.mathlinks.ro/Forum/viewtopic.php?t=22810 . Some other topics should exist, too. Darij

Let $ \frac{m^2 + n^2}{mn - 1} = k $ for some $ k \in \mathbb{Z}^+ $. We can write this as $ m^2 - knm + (n^2 + k) = 0 $ and so $ m $ is a solution to the quadratic in $ x $, $ x^2 - knx + (n^2 + k) = 0 $. The other solution is $ m' = kn - m = \frac{n^2 + k}{m} $. Now clearly $ m \ne n $, so assume WLOG that $ m > n $. For now, assume that $ n > 1 $. These assumptions imply that $ n(m - n) \ge 2 \Longrightarrow m(mn - 2) > n^2 $. Rearranging this means that $ n(m^2 + n^2) < 2m(mn - 1) \Longrightarrow m' = kn - m < m $. So if we consider the process of changing pairs $ (m, n) $ into a new pair $ (km - n, n) $ (rearranged so that the first coordinate is the larger of the two) until one of the elements of the pair is $ 1 $, this process clearly terminates at either $ (2, 1) $ or $ (3, 1) $. Since $ k $ has stayed the same throughout this process, this argument implies that $ k = 5 $. This implies that all solutions are given by taking the sequences $ x_1 = 1, x_2 = 2, x_n = 5x_{n - 1} - x_{n - 2} $ and $ y_1 = 1, y_2 = 3, y_n = 5y_{n - 1} - y_{n - 2} $ and taking pairs $ (x_m, x_{m + 1}) $ and $ (y_m, y_{m + 1}) $ for any $ m \in \mathbb{N}. $ The explicit forms of these pairs can then be found in a standard fashion with generating functions or just taking the characteristic polynomial of the linear recurrences.

Wolstenholme wrote: Let $ \frac{m^2 + n^2}{mn - 1} = k $ for some $ k \in \mathbb{Z}^+ $. We can write this as $ m^2 + knm + (n^2 + k) = 0 $ and so $ m $ is a solution to the quadratic in $ x $, $ x^2 + knx + (n^2 + k) = 0 $. The other solution is $ m' = kn - m = \frac{n^2 + k}{m} $. Now clearly $ m \ne n $, so assume WLOG that $ m > n $. For now, assume that $ n > 1 $. . The correct is $m^2-kmn+n^2+k-0$

$x^2+y^2=k(xy-1)$ Set $xy-1=a$ $x^2+y^2=ka$ We want to solve this system... $x=\dfrac{a+1}{y}$ So put $x$ at the equation and will get.. $y^4-kay^2+(a+1)^2=0$ $D=k^2a^2-4(a+1)^2=w^2$ , (then $y^2=\dfrac{ka+-w}{2}$) $(ka)^2=(2a+2)^2+w^2$ pythagorian triples and the rest is easy... Δημήτρης

I claim the only pairs $(m,n)$ for which $mn-1 \mid m^2+n^2$ are $\boxed{(m,n)=(2,1),(3,1),(1,2),(1,3)}$. If $mn-1 \mid m^2+n^2$ we must surely have $$\frac{m^2+n^2}{mn-1}=c~~~c\in\mathbb{Z}.$$Now this implies that we have $m^2+n^2=c(mn-1)$ or $m^2-cnm+n^2+c^2=0$. Now let $(m,n)$ be a solution to this diophantine, where $m+n$ is minimized. If $(m,n)$ is a solution to the diophantine, it must surely be true that $(m',n)$ is a solution to the equation, where $m'=cn-m=\frac{n^2+c}{m}$. Clearly, $m'$ is positive, since $c$ is positive, so $cn-m>0$. Since $m'\in\mathbb{Z}, cn-m \ge 1$. Now clearly $m \ne n$, so without loss of generality, $m>n$. Now I claim that $n=1$. For sake of contradiction, assume that $n \ne 1$. Since $n$ is a positive integer, we must have $n>1 \implies m>n>1$. Now by minimality of $m+n$, we must have $$m+n \le m'+n \implies m \le m'.$$However, observe that since $m>n>1$, $$n(m-n) \ge 2 \implies mn-2 \ge n^2 \implies m(mn-2) \ge mn^2 >n^3 \implies n(m^2-n^2) >2m$$$$\implies m^2n >2m+n^3 \implies 2m^2n-2m >m^2n+n^3 \implies 2m(mn-1) > n(m^2+n^2) \implies m>kn-m=m'$$a contradiction. Thus, $n=1$. Now since $n=1$, we must have $$\frac{m^2+n^2}{mn-1}=\frac{m^2+1}{m-1}=(m+1)+\frac{2}{m-1}$$Clearly this an integer if and only if $m-1 \mid 2$, and since $m \ge 0$ we must clearly have $m=2$ or $m=3$. Thus, the only solutions for which $m>n$ is $(2,1)$ and $(3,1)$. Now since the expression is symmetric about $m$ and $n$ the only pairs $(m,n)$ for which $mn-1 \mid m^2+n^2$ is $\boxed{(2,1),(3,1),(1,2),(1,3)}. \blacksquare$ P.S: 1000th post!

realquarterb wrote: I claim the only pairs $(m,n)$ for which $mn-1 \mid m^2+n^2$ are $\boxed{(m,n)=(2,1),(3,1),(1,2),(1,3)}$. If $mn-1 \mid m^2+n^2$ we must surely have $$\frac{m^2+n^2}{mn-1}=c~~~c\in\mathbb{Z}.$$Now this implies that we have $m^2+n^2=c(mn-1)$ or $m^2-cnm+n^2+c^2=0$. Now let $(m,n)$ be a solution to this diophantine, where $m+n$ is minimized. If $(m,n)$ is a solution to the diophantine, it must surely be true that $(m',n)$ is a solution to the equation, where $m'=cn-m=\frac{n^2+c}{m}$. Clearly, $m'$ is positive, since $c$ is positive, so $cn-m>0$. Since $m'\in\mathbb{Z}, cn-m \ge 1$. Now clearly $m \ne n$, so without loss of generality, $m>n$. Now I claim that $n=1$. For sake of contradiction, assume that $n \ne 1$. Since $n$ is a positive integer, we must have $n>1 \implies m>n>1$. Now by minimality of $m+n$, we must have $$m+n \le m'+n \implies m \le m'.$$However, observe that since $m>n>1$, $$n(m-n) \ge 2 \implies mn-2 \ge n^2 \implies m(mn-2) \ge mn^2 >n^3 \implies n(m^2-n^2) >2m$$$$\implies m^2n >2m+n^3 \implies 2m^2n-2m >m^2n+n^3 \implies 2m(mn-1) > n(m^2+n^2) \implies m>kn-m=m'$$a contradiction. Thus, $n=1$. Now since $n=1$, we must have $$\frac{m^2+n^2}{mn-1}=\frac{m^2+1}{m-1}=(m+1)+\frac{2}{m-1}$$Clearly this an integer if and only if $m-1 \mid 2$, and since $m \ge 0$ we must clearly have $m=2$ or $m=3$. Thus, the only solutions for which $m>n$ is $(2,1)$ and $(3,1)$. Now since the expression is symmetric about $m$ and $n$ the only pairs $(m,n)$ for which $mn-1 \mid m^2+n^2$ is $\boxed{(2,1),(3,1),(1,2),(1,3)}. \blacksquare$ P.S: 1000th post! This is wrong of course you've shown using vieta jumping that the smallest solution should have $n=1$ but there is nothing about the bigger once however applying vieta jumping conversly generates the other solutions(There are infinity of them for example $(9,2)$ works too.)

Here's my solution: ${\color{red} \rule{\linewidth}{0.5mm} }$ So first we will claim that if Claim: $\frac{a^2+b^2}{ab-1}=k$ then $k=5$ Proof: First we use a Lemma 1: If $\frac{A^2+B^2}{AB-1}=n$ has $(A,B)$ as a solution then $(A,\frac{B^2+n}{A})$ is also an integer solution. Proof: The solution to $\frac{A^2+B^2}{AB-1}=n$ will also be a solution to $x^2-nBx+(B^2+n)=0$.By our initial assumption $A$ is obviously a root,and by vieta's relations $\frac{B^2+n}{A}$ is also a root.Putting this in the equation gives the result as $n$ so this is another root. Lemma 2:- If $A>B \ge 3$ then $\frac{b^2+n}{a}<b$ where $min(a,b)=(A,B)$ Proof: Since $b \ge 3$ we must have $b^2-1>2b$. Using this: $\frac{b^3+b}{b^2-1}=b+\frac{2b}{b^2-1}<a->b^3+b<ab^2-a->a+b^3<ab^2-b->\frac{a+b^3}{ab-1}<b->\frac{b^2+n}{a}<b$ as required. So the only cases we need to check are $b=1,2$ Now we check case by case:- 1)$b=1$,then we must have $\frac{2}{a-1} \in N$ so the only possible value of $n=5$ 2)$b=2$,then $\frac{17}{a-1} \in N$ and checking yields $n=5$ Hence proved. ${\color{red} \rule{\linewidth}{0.5mm} }$ Now we want to solve the equation $\frac{m^2+n^2}{mn-1}=5$ so we get $m^2+m^2=5(mn+1)$ and then suppose that $(m,n)$ is the smallest root. Now by vieta's relations the other root will be $(m,n)->(5m-n,m)$ yielding infinite solutions to the equation. So to find its explicit formula we need to calculate ${a_1},{b_1}$ Now as @realquaterb showed,we will show that the smallest solutions must have $n=1$. So,If $mn-1 \mid m^2+n^2$ we must have$$\frac{m^2+n^2}{mn-1}=c$$,And by this we get the quadratic:$m^2+n^2=c(mn-1)$ or $m^2-cnm+n^2+c^2=0$. Now let $(m,n)$ be a solution to this diophantine, where $m+n$ is minimal.And also assume that the other root of this quadratic is $M$ Now since $m \ne n$, so WLOG, $m>n$. Now we show that $n=1$. FTSOC, assume that $n \ne 1$. Since $n$ is a positive integer, we must have $n>1 \implies m>n>1$. Now since $m+n$ is minimum, we must have$$m+n \le M+n \implies m \le M.$$However, observe that since $m>n>1$,$$n(m-n) \ge 2 \implies mn-2 \ge n^2 \implies m(mn-2) \ge mn^2 >n^3 \implies n(m^2-n^2) >2m$$$$\implies m^2n >2m+n^3 \implies 2m^2n-2m >m^2n+n^3 \implies 2m(mn-1) > n(m^2+n^2) \implies m>kn-m=M$$a contradiction. Hence, $n=1$. So we obtain $(1,2),(1,3)$ and it's permutations to be ${a_1},{b_1}$ respectively. Now all the solutions generated by this sequence are unique since if say $(m,n)$ was a solution then $(5m-n,m)$ is greater than our previous solution since $5m-n>5m-m>4m>m,m>n$ Therefore, $\boxed{({a_1},{b_1})=(1,2),(1,3),(2,1),(3,1) \text{ and the explicit formula is } 5a_n-b_n=a_{n+1},b_n=a_{n-1}}$ ${\color{black} \rule{\linewidth}{0.5mm} }$

The answer is the following two classes of solutions, up to symmetry: $(a_k, a_{k+1})$ where $a_1 = 1, a_2 = 2, a_n = 5a_{n-1} - a_{n-2}$. $(b_k, b_{k+1})$ where $b_1 = 1, b_2 = 3, b_n = 5b_{n-1} - b_{n-2}$. Assume that $(m, n)$ is a solution to the equation $$\frac{m^2+n^2}{mn-1} = c$$for some fixed positive integer $c$, which we will call $\dagger$. Then, $$m^2+n^2=c(mn-1),$$which expands to $$m^2+n^2-cmn+c=0.$$As a result, if $(m, n)$ is a solution to $\dagger$, so is $(m', n) = (cn-m, n)$, a transformation which we will call $T$. Now, suppose that $m+n$ is minimal across all solutions $(m, n)$. Then $$m' = \frac{n^2+c}m \geq m \iff m^2-n^2 \leq \frac{m^2+n^2}{mn-1}.$$With some algebra, this expands to $n(m^2-n^2) \leq 2m$. However, consider the chain of inequalities $$mn(m-n) < n(m+n)(m-n) \leq 2m,$$which implies that $n(m-n)\leq 1$ for this minimal pair. It follows that $(m, n) = (2, 1)$ is the only solution to $\dagger$, which yields the constant $c=5$. It remains to classify all solutions. All solutions can be obtained by alternating applying $T^{-1}$ and inverting $(m, n) \to (n, m)$ (as applying any two of these operations consecutively returns to the identity.) This yields two classes of solutions, up to symmetry: $(a_k, a_{k+1})$ where $a_1 = 1, a_2 = 2, a_n = 5a_{n-1} - a_{n-2}$. $(b_k, b_{k+1})$ where $b_1 = 1, b_2 = 3, b_n = 5b_{n-1} - b_{n-2}$. These are all the solutions, the first class obtained by inverting the base solution $(2, 1)$ to $(1, 2)$ and applying $T^{-1}$ and performing an inversion alternately, and the second class obtained by performing $T^{-1}$ on the base solution and inverting it, yielding $(1, 3)$, before we apply the alternating series of operations. Notice that because some series of operations $T$ and inversions will transform any solution into $(2, 1)$ and thus have $c=5$, this classifies all solutions.

Essentially identical to 88IMO6. Suppose $(m,n)$ is a solution to $\tfrac{m^2+n^2}{mn-1}=k$ for some positive integer $k.$ We have \[m^2+n^2=k(mn-1) \implies m^2-m(kn)+(n^2+k).\]It follows that $(m',n)$ is also a solution, where $m'=\tfrac{n^2+k}{m} = kn-m.$ Suppose that $m+n$ is minimal across all solutions $(m,n).$ Then \[m'=\frac{n^2+k}{m} \geq m \Longleftrightarrow n^2+k \geq m^2 \Longleftrightarrow m^2-n^2 \leq \frac{m^2+n^2}{mn-1}.\]A bit of algebra reduces this to \[(m^2-n^2)(mn-1) \leq m^2+n^2 \implies n(m^2-n^2)=n(m-n)(m+n) \leq 2m.\]Observe \[mn(m-n) < n(m-n)(m+n) \leq 2m,\]So $n(m-n) \leq 1.$ This forces $(m,n)=(2,1),$ which gives $k=5.$ From here, classifying all solutions is not hard. We can generate solutions with our transformation $(kn-m, n) \to (m,n),$ and inverting the pair $(m,n) \to (n,m).$ It follows we can obtain all solutions with: 1. $(a_k, a_{k+1}),$ where $a_1=1,$ $a_2=2,$ $a_n=5a_{n-1}-a_{n-2}.$ 2. $(b_k, b_{k+1}),$ where $b_1=1,$ $b_2=3,$ $b_n=5b_{n-1}-b_{n-2}.$ The first solution is attained by alternating between a transformation and inversion from the base pair $(1,2),$ and the second solution is attained by applying a transformation and then an inversion from the base pair $(2,1),$ and then continuing by alternating between transformations and inversions. Observe this classifies all solutions, because a sequence of inversions and transformations will take any solution to our original base pair $(2,1),$ as desired.

Just use vieta jumping to prove m^2 + n^2 / mn-1 Is integer if and only if it is eql to 5 now its time for diphantine