## from apmc

For discussing Olympiad Level Number Theory problems
the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

### from apmc

find triples (p,q,n) with p,q primes and n an integer which is greater or equal 1
satisfying the awkward( ) relation
p(p+1)+q(q+1)=n(n+1)
the arrivals
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

Moon
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Contact:

### Re: from apmc

Nice problem:
Hint (I'll post complete solution later)
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

learn how to write equations, and don't forget to read Forum Guide and Rules.

Avik Roy
Posts: 156
Joined: Tue Dec 07, 2010 2:07 am

### Re: from apmc

Some basic number theory also performs well
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

### Re: from apmc

(2,2,3) perhaps a solution also.
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

Moon
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Contact:

### Re: from apmc

Yup...the solutions are $(p,q,n)=(2,2,3),(5,3,6)$.

Case 1: $p=q$
We have $2p(p+1)=n(n+1)$.

Case 1(a): $p | n$
So, $n \geq 2p \iff n+2 \geq 2(p+1)$ ($n=p$ is not possible). We also have $2(p+1)=k(n+1)$. So, $k(n+1) \leq n+2$. Checking some values of $k$ we can see that this case is not possible.

Case 1(b): $p |(n+1)$
So, $(n+1) \geq 2p \iff n+3 \geq 2(p+1)=kn \iff (k-1)n \leq 3$. Only $k=1$ is possible. We have $(p,q,n)=(2,2,3)$.

Case 2: $p >q$
The equation rearranges to $p(p+1)=(n-q)(n+q+1)$.

Case 2(a): $p | (n-q)$
Then $p \leq (n-q) \iff p+1 \leq n-q+1 < n+q+1$. Contradiction!

Case 2(b): $p | (n+q+1)$
As $n-q< n+q+1$, $n+q+1 \geq 2p$. Then we have $n-q <p \iff n+q+1 <p+2q+1 <3p$.

Finally we have $3p>n+q+1 \geq 2p \iff n+q+1=2p$. So, $2(n-q)=p+1$. From these two equalities we have $3n-5q=3$. So $3 |q$ and recall that $q$ is a prime. So $q=3$. From the equalities we also have $4q+3=3p$; so, $p=5$.
We are done!

Remark: When writing more official solution you can not just write, "it is easy to check that..." you must complete write how to check as well.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

learn how to write equations, and don't forget to read Forum Guide and Rules.

Avik Roy
Posts: 156
Joined: Tue Dec 07, 2010 2:07 am

### Re: from apmc

I just got a combinatorial proof of the problem
The given relation can be written as: $\begin{pmatrix} n+1\\2 \end{pmatrix} = \begin{pmatrix} p+1\\2 \end{pmatrix} +\begin{pmatrix} q+1\\2 \end{pmatrix}$
Now, since $p<n$, lets consider that we choose $n-p$ elements from available $n+1$ elements and keep them aside in choosing elements. So we have $p+1$ elements to choose from. In the following cases, we choose elements from the kept aside $n-p$ elements in all possible combinations to keep or not to keep them in our selection to complete the quota. However, we have only $2$ elements to select, so $n-p$ can't exceed $2$. Choosing $n-p=2$, we have the following equation to satisfy:$\begin{pmatrix} p+1\\2 \end{pmatrix}+2\begin{pmatrix} p+1\\1 \end{pmatrix}+1=\begin{pmatrix} n+1\\2 \end{pmatrix}$
and putting $n=p+2$ here leads one to complete gibberish. Hence $n=p+1$ is to satisfy. Comaring the given equation with the identity: $\begin{pmatrix} n+1\\r \end{pmatrix} = \begin{pmatrix} n\\r \end{pmatrix} +\begin{pmatrix} n\\r-1 \end{pmatrix}$
we hereby obtain
$\begin{pmatrix} q+1\\2 \end{pmatrix} = \begin{pmatrix} p+1\\1 \end{pmatrix}$
$\Rightarrow q(q+1) = 2(p+1)$
Now, we have to consider the following cases-
C1: $q=2$ which leads to the solution $(2,2,3)$
C2: $q|p+1$ implying the following set of equations:
$p+1 = kq$
$q+1 = k.2$
$p+q+2 = k(q+2)$
$\Rightarrow k = 1 + \frac {p}{q+2}$
since $p$ is a prime $p=q+2$ and $k=2$
This leads us to the solution $(5,3,6)$
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

### Re: from apmc

oow!! awesome!! what make you approching like this?? very cool instead.appreciating.
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

Avik Roy
Posts: 156
Joined: Tue Dec 07, 2010 2:07 am

### Re: from apmc

@the arrivals, whom did you address??
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

Moon
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Contact:

### Re: from apmc

The approach is really unorthodox and cool!
However, to me these explanations are not clear.
Avik Roy wrote:Now, since $p<n$, lets consider that we choose $n-p$ elements from available $n+1$ elements and keep them aside in choosing elements. So we have $p+1$ elements to choose from. In the following cases, we choose elements from the kept aside $n-p$ elements in all possible combinations to keep or not to keep them in our selection to complete the quota. However, we have only $2$ elements to select, so $n-p$ can't exceed $2$. Choosing $n-p=2$
BTW you need not use \pmatrix, you may use \binom or \dbinom
I mean $\dbinom{n+1}{2}$
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin