A number theory problem from the British Math Olympiad

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A number theory problem from the British Math Olympiad

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: British Math Olympiad, 2006/2007, round 1, problem 6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

35 posts

#1 h Mar 28, 2025, 8:39 PM

Y by

I am a little surprised to find that I am (so far) unable to solve this little problem:

Quote:

Let $n$ be an integer. Show that, if $2 + 2 \sqrt{1+12n^2}$ is an integer, then it is a perfect square.

I set $k := \sqrt{1+12n^2}$ . If $2 + 2 \sqrt{1+12n^2}$ is an integer, then $k (=\sqrt{1+12n^2})$ is at least rational, so that $1 + 12n^2$ must be a perfect square then. Using Conway's topograph method, I have found out that the smallest non-negative pairs $(n, k)$ for which this happens are $(0,1), (2,7), (28,97)$ and $(390, 1351)$ , and that, for every such pair $(n,k)$ , the "next" such pair can be calculated as
$\begin{bmatrix} 7 & 2 \\ 24 & 7 \end{bmatrix} \begin{bmatrix} n \\ k \end{bmatrix} .$ The eigenvalues of that matrix are irrational, however, so that any calculation which uses powers of that matrix is a little cumbersome. There must be an easier way, but I cannot find it. Can you?

Thank you.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3789 posts

vsamc

#2 h Mar 28, 2025, 9:03 PM • 1 Y

Y by centslordm

Try to write the general solution $(n, k)$ using pell equation theory, and then consider $2+2k$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

35 posts

#3 h Mar 28, 2025, 9:12 PM

Y by

Thank you for your suggestion. I am aware that there is a Pell equation here, but I am not sure if I can make any progress using the corresponding theory. That theory also tells us how to generate further solutions from a given solution, in a way that is quite parallel to the matrix-vector multiplication in my post. I cannot see anything beyond that which would be helpful.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

75 posts

#4 h Mar 29, 2025, 1:47 PM • 1 Y

Y by Rainbow1971

The solution is surprisingly simple:

Let $2 + 2\sqrt{1+12n^2} = 2m$ (because it is even), where $m$ is a positive integer.

Dividing both sides by 2 and subtracting 1 from both sides, we get

$m - 1 = \sqrt{1+12n^2}$
Squaring both sides, we get

$(m-1)^2 = 1 + 12n^2$
so

$12n^2 = m(m-2).$
Since the left side is even, $m$ is even. Let $m = 2k$ , where $k$ is a positive integer.

The equation becomes

$12n^2 = 2k(2k-2)$
or

$3n^2 = k(k-1).$
Since $(k, k-1) = 1$ and the left side is divisible by 3, exactly one of $k$ and $k-1$ is divisible by 3.

We consider two cases:

Case 1: $k$ is divisible by 3, so $k-1$ is a square, which is impossible because $k-1 \equiv 2 \pmod{3}$ .

Case 2: $k-1$ is divisible by 3, so $k$ is a square. Let $k = t^2$ , where $t$ is a positive integer.

Then $2 + 2\sqrt{1+12n^2} = 2m = 4k = (2t)^2$ , which is a square.

This post has been edited 1 time. Last edited by pooh123, Mar 29, 2025, 1:49 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ektorasmiliotis

110 posts

ektorasmiliotis

#5 h Mar 29, 2025, 2:47 PM

Y by

another problem from a competition called Kurshak(i think)
if 2 + 2sqrt(28n^2+1) is integer,show that is a perfect square
i solved it with pell,i think its the same with this problem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

35 posts

#6 h Mar 29, 2025, 3:46 PM

Y by

Thank you, pooh123, your solution is indeed a nice one! A question to ektorasmiliotis: What exactly do you mean by "I solved it with pell"?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ektorasmiliotis

110 posts

ektorasmiliotis

#7 h Mar 29, 2025, 5:01 PM

Y by

Rainbow1971 wrote:

Thank you, pooh123, your solution is indeed a nice one! A question to ektorasmiliotis: What exactly do you mean by "I solved it with pell"?

using pell's equation : https://en.wikipedia.org/wiki/Pell%27s_equation
for your exercise :
M=2+2sqrt(12n^2+1)
so sqrt(12n^2+1)=M/2 -1, Set X= M/2 -1
X^2-12n^2=1 with (Xo,No)=(7,2)
So Xn=1/2(((7+2sqrt(12))^n +(7-2sqrt(12))^n)
see that 7+2sqrt(12)=(2+sqrt(3))^2 ........
M=((2+sqrt(3))^n+(2-3sqrt(3))^n)^2,so M is always a perfect square by Binomial theorem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

35 posts

#8 h Mar 29, 2025, 6:41 PM

Y by

Thank you for the clarification. There is one line in it which surprises me:

$X_n=\tfrac{1}{2} \big( (7+2\sqrt{12})^n + (7-2\sqrt{12})^n)\big).$
I did not know that it is so easy to calculate (the first component of) the $n$ th solution pair, particularly without recursion, and I cannot find any remark in that direction in the Wikipedia article. However, numerical calculation confirms your claim. Can you give me a source that would explain the line above?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3789 posts

vsamc

#9 h Mar 29, 2025, 6:55 PM • 1 Y

Y by centslordm

I'm surprised you knew about Conway's topograph method but not the general formula. If $d > 1$ is squarefree, and $x^2 -dy^2 = 1$ has primitive (meaning "smallest", based on, say, $x$ ) solution $(x_1, y_1)$ in positive integers, then the $n$ 'th largest solution $(x_n, y_n)$ satisfies $x_n + y_n\sqrt{d} = (x_1+y_1\sqrt{d})^n$ . The reason this even works is because $x^2-dy^2 = (x+y\sqrt{d})(x-y\sqrt{d})$ , so $(x_n+y_n\sqrt{d})(x_n-y_n\sqrt{d}) = (x_1+y_1\sqrt{d})^n(x_1-y_1\sqrt{d})^n = (x_1^2-dy_1^2)^n = 1$ . You can find the proof that this is all solutions on wikepedia (sketch: multiply a solution $x+y\sqrt{d}$ by $x_1-y_1\sqrt{d}$ and induct down)

This post has been edited 1 time. Last edited by vsamc, Mar 29, 2025, 6:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

35 posts

#10 h Mar 29, 2025, 7:04 PM

Y by

Lots of surprises in this thread... Thank you, vsamc. You mention that
$x_n + y_n\sqrt{d} = (x_1+y_1\sqrt{d})^n,$ which is fine, but calculating $x_n$ still seems to require expanding the right-hand side of the equation and collecting the terms that are free of square roots. ektorasmiliotis, however, mentioned a way to calculate $x_n$ directly. Maybe ektorasmiliotis' method follows from what you, vsamc, wrote, but so far I don't see that...

This post has been edited 1 time. Last edited by Rainbow1971, Mar 29, 2025, 7:11 PM
Reason: minor error

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3789 posts

vsamc

#11 h Mar 29, 2025, 7:24 PM • 2 Y

Y by Rainbow1971, centslordm

$x_n + y_n\sqrt{d} = (x_1+y_1\sqrt{d})^n$ , it follows by taking the "radical conjugate" of both sides that
$x_n - y_n\sqrt{d} = (x_1-y_1\sqrt{d})^n$
so $x_n = \frac{(x_1+y_1\sqrt{d})^n + (x_1-y_1\sqrt{d})^n)}{2}$ and $y_n = \frac{(x_1+y_1\sqrt{d})^n - (x_1-y_1\sqrt{d})^n}{2\sqrt{d}}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

35 posts

#12 h Mar 29, 2025, 7:28 PM

Y by

Ah, now I see the connection. Thanks a lot.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ektorasmiliotis

110 posts

ektorasmiliotis

#13 h Mar 29, 2025, 8:33 PM

Y by

vsamc wrote:

I'm surprised you knew about Conway's topograph method but not the general formula. If $d > 1$ is squarefree, and $x^2 -dy^2 = 1$ has primitive (meaning "smallest", based on, say, $x$ ) solution $(x_1, y_1)$ in positive integers, then the $n$ 'th largest solution $(x_n, y_n)$ satisfies $x_n + y_n\sqrt{d} = (x_1+y_1\sqrt{d})^n$ . The reason this even works is because $x^2-dy^2 = (x+y\sqrt{d})(x-y\sqrt{d})$ , so $(x_n+y_n\sqrt{d})(x_n-y_n\sqrt{d}) = (x_1+y_1\sqrt{d})^n(x_1-y_1\sqrt{d})^n = (x_1^2-dy_1^2)^n = 1$ . You can find the proof that this is all solutions on wikepedia (sketch: multiply a solution $x+y\sqrt{d}$ by $x_1-y_1\sqrt{d}$ and induct down)

and the primitive solution is not (1,0),(-1,0)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ektorasmiliotis

110 posts

ektorasmiliotis

#14 h Apr 3, 2025, 8:25 AM

Y by

another solution ,it's much easier i think..

sqrt(12n^2+1)=2k+1
12n^2+1=4k^2+4k+1
3n^2=k(k+1) but (k,k+1)=1
1)if k=x^2 and k+1=3y^2,then x^2-3y^2=-1 and we use mod 4,no solutions
2)if k=b^2 and k+1=a^2
M=2+2sqrt(12n^2+1)=2 +2(2k+1)=2 +4k +2=4(k+1)=4a^2=(2a)^2

**I just saw post 4, we have similar solutions.

This post has been edited 1 time. Last edited by ektorasmiliotis, Apr 3, 2025, 8:30 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a