47p^2+1 is a Perfect Square

Altheman

Find all primes $p$ such that $47p^2+1$ is a perfect square.

**Posted:** Mon Jun 09, 2008 11:40 am

_________________
-Alex
Altheman's Problem Column

FantasyLover

lets say that $47p^2 + 1 = a^2$ .

then $47p^2 = a^2 - 1 = (a + 1)(a - 1)$

since 47 is a prime number, 47 is either a+1 or a-1, and $p^2$ should be another.

if 47=a-1,a=48, $p^2 = a + 1 = 49.$ so p=7.

answer : 7

**Posted:** Mon Jun 09, 2008 11:44 am

_________________
AAST 2013

Altheman

**Posted:** Mon Jun 09, 2008 12:03 pm

_________________
-Alex
Altheman's Problem Column

resurrection

P could be a multiple of 47...

**Posted:** Mon Jun 09, 2008 1:10 pm

Carbon57

Continuing on FantasyLover's solution...

If you let $a+1=47p$ and $a-1=p$ , you get non-integer solutions, so that's not possible.

If you let $a+1=p$ and $a-1=47p$ , you also get non-integer solutions.

If you let $a+1=47p^2$ and $a-1=1$ , you get non-integer solutions.

If you let $a+1=1$ and $a-1=47p^2$ , you get non-integer solutions.

These are all of the possibilities since 47 is prime...so 7 is the only possible answer.

**Posted:** Mon Jun 09, 2008 3:47 pm

t0rajir0u

Note that $\gcd(a + 1, a - 1) | 2$ . Verify that $p = 2$ doesn't work, so $\gcd(a + 1, a - 1) = 1$ and we only have two cases to check instead of four.

**Posted:** Mon Jun 09, 2008 4:22 pm

_________________
Annoying Precision (http://qchu.wordpress.com/)

Altheman

Right. It is clear that $47$ divides one of those factors individually, but you have to allocate the other factors as well.

$a-1\le a+1\le 2(a-1)$ and that eliminates all of the other cases.

**Posted:** Tue Jun 10, 2008 3:58 pm

_________________
-Alex
Altheman's Problem Column

FantasyLover

**Posted:** Tue Jun 10, 2008 3:59 pm

_________________
AAST 2013

itiselizabeth · P versus NP Offline Joined: 23 Jul 2009 Posts: 33

**Posted:** Sat Jul 25, 2009 4:03 am

_________________

1=2

**Posted:** Sat Jul 25, 2009 5:19 am

_________________
MC Chapter happened on 1/30. Me and my friends have been coaching the people that were in the top 20 since November.

itiselizabeth · P versus NP Offline Joined: 23 Jul 2009 Posts: 33

$\sqrt {47}\ = \ 6 + \cfrac1{1 + \cfrac1{5 + \cfrac1{1 + \cfrac1{12 + \cdots}}}}$

Set $q_0 = 6,\ q_1 = 1,\ q_2 = 5,\ q_3 = 1,\ q_4 = 12,\ \ldots.$

The convergents are terms in the sequence $\left\langle\frac {a_i}{b_i}\right\rangle_{i\, = \,0}^\infty$ where the $a_i$ and $b_i$ are calculated as follows.

$a_0\ = \ q_0\ = \ 6$

$a_1\ = \ q_1a_0 + 1\ = \ 7$

$a_2\ = \ q_2a_1 + a_0\ = \ 41$

$a_3\ = \ q_3a_2 + a_1\ = \ 48$

$\vdots$

$a_{i + 2}\ = \ q_{i + 2}a_{i + 1} + a_i$

$b_0\ = \ 1$

$b_1\ = \ q_1\ = \ 1$

$b_2\ = \ q_2b_1 + b_0\ = \ 6$

$b_3\ = \ q_3b_2 + b_1\ = \ 7$

$\vdots$

$b_{i + 2}\ = \ q_{i + 2}b_{i + 1} + b_i$

Now you just have to try $a_i^2 - 47b_i^2$ until you find a pair for which the expression equals 1; these will be the fundamental solution. But in this particular problem, you know that $b_i$ has to be prime, so you know you can pick $b_3=7$ right away. Very Happy

This is a technique I only learned recently so I may not be terribly good at it yet. Wink

**Posted:** Sat Jul 25, 2009 7:30 am

_________________

t0rajir0u

The algorithm is given here. There is a very elegant way to organize the work in a table that makes the computation extremely fast, but it's a bit hard to describe in words.

**Posted:** Sat Jul 25, 2009 9:30 am

_________________
Annoying Precision (http://qchu.wordpress.com/)