number theory

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

number theory

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

104 posts

#1 h Mar 31, 2016, 1:56 PM • 2 Y

Y by Adventure10, Mango247

Find all pairs $(n;p)$ of natural numbers $n$ and prime numbers $p$ , satisfying the equation $p(p-1)=2(n^3+1)$

Z K Y

The post below has been deleted. Click to close.

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

830 posts

#2 h Mar 31, 2016, 2:50 PM • 2 Y

Y by Adventure10, Mango247

Lemma: if $ab=cd$ and $\gcd(a,b)=\gcd(c,d)=1$ and $a,b,c,d \ne 1$ then $a=c,b=d$ or $a=d,b=c$
case 1: $n^2-n+1 \vdots 2 \Rightarrow p(p-1)\vdots 4 \Rightarrow p=2 \Rightarrow n=0$
case 2: $n^2-n+1 \not\vdots 2$
if $n+1 \not\vdots 3$ then $\gcd(2(n+1),n^2-n+1)=\gcd(2(n+1),3n)=1$ and we have $\gcd(p,p-1)=1$ so use the lemma we have
$p-1=2(n+1)$ and $p=n^2-n+1$ or $p-1=n^2-n+1$ and $p=2(n+1) \Rightarrow n^2-3n-1=1$ or $-1$
if $n+1\vdots 3$ then $n=3k+2$ put it in the equation and do similarly to case 2

This post has been edited 2 times. Last edited by thuanz123, Mar 31, 2016, 2:55 PM

Z K Y

The post below has been deleted. Click to close.

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

104 posts

#3 h Mar 31, 2016, 2:57 PM • 1 Y

Y by Adventure10

Quote:

case 1: $n^2-n+1 \vdots 2 \Rightarrow p(p-1)\vdots 4 \Rightarrow p=2 \Rightarrow n=0$

from $p(p-1)\vdots 4$ it doesn't follow that $p=2$ because it is enough that $p=4k+1$ and by Dirichlet theorem there exists infinitly many such primes

This post has been edited 2 times. Last edited by proximo, Mar 31, 2016, 2:58 PM

Z K Y

The post below has been deleted. Click to close.

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

381 posts

#4 h Mar 31, 2016, 3:00 PM • 3 Y

Y by helol, Adventure10, Mango247

Also, the lemma is wrong: $6\cdot 7=3\cdot 14$

Z K Y

The post below has been deleted. Click to close.

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

2541 posts

#5 h Mar 31, 2016, 4:29 PM • 2 Y

Y by Adventure10, Mango247

If p=2, n is not a natural number...

Z K Y

The post below has been deleted. Click to close.

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

4071 posts

#6 h Mar 31, 2016, 4:35 PM • 2 Y

Y by Adventure10, Mango247

Case $1)$ $p\leq n+1$
We get $LHS \leq n^2+n$ , so $2(n^3+1) \leq n^2+n$ which is false when $n\in \mathbb{Z}^+$
Case $2)$ $p>n+1>2$ , since $n=1$ is not a solution
Since $p\mid 2(n+1)(n^2-n+1)$ and $p>n+1$ , $p$ is odd number
So $p \mid n^2-n+1$
So there exist positive integer $k$ such that $n^2-n+1=pk$
Give us $p=2(n+1)k+1$ , so $n^2-n+1=2(n+1)k^2+k$
So $n^2-(2k^2+1)n-(2k^2+k-1)=0$ , so $\triangle_n$ is perfect square
So $(2k^2+1)^2+4(2k^2+k-1)=4k^4+12k^2+4k-3$ is perfect square
But $(2k^2+4)^2=4k^4+16k^2+16 >4k^4+12k^2+4k-3 >(2k^2+3)^2=4k^4+12k^2+9$ when $k>3$
So $k\leq 3$ and we need to check this trivial case

Z K Y

The post below has been deleted. Click to close.

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

104 posts

#7 h Mar 31, 2016, 4:40 PM • 2 Y

Y by Adventure10, Mango247

Yes, that's right. If you are interested the answer is $n=20$ and $p=127$

Z K Y

The post below has been deleted. Click to close.

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

4071 posts

#8 h Mar 31, 2016, 4:49 PM • 2 Y

Y by Adventure10, Mango247

What is the source of this problem ...

Z K Y

The post below has been deleted. Click to close.

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

104 posts

#9 h Mar 31, 2016, 4:52 PM • 3 Y

Y by ThE-dArK-lOrD, Adventure10, Mango247

Belarusian National Olympiad year 2012

Z K Y

The post below has been deleted. Click to close.

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

3 posts

#10 h Aug 14, 2016, 6:01 PM • 2 Y

Y by Adventure10, Mango247

Got n=20 and p=127 for this one

Z K Y

The post below has been deleted. Click to close.

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

241 posts

#11 h Nov 27, 2016, 12:43 PM • 2 Y

Y by Adventure10, Mango247

Similar to BMO 2005.

Z K Y

The post below has been deleted. Click to close.

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

HadjBrahim-Abderrahim

169 posts

HadjBrahim-Abderrahim

#14 h Nov 27, 2016, 1:37 PM • 2 Y

Y by Adventure10, Mango247

thuanz123 wrote:

Lemma: if $ab=cd$ and $\gcd(a,b)=\gcd(c,d)=1$ and $a,b,c,d \ne 1$ then $a=c,b=d$ or $a=d,b=c$

Let, $a=a_1^{\alpha_1}a_2^{\alpha_2}\cdots p_k^{\alpha_k}$ and, $b=b_1^{\beta_1}b_2^{\beta_2}\cdots b_l^{\beta_l}$ where $a_1<a_2<\cdots<a_k$ and $b_1<b_2<\cdots<b_l$ are prime numbers, also, $a_1,a_2,\ldots,a_k$ and $b_1,b_2,\ldots, b_l$ are all positive integers. We mean by $\gcd(a,b)=1$ that, all the $a_i$ 's are different to all the $b_j$ 's where $i=1,2,\ldots,k$ and, $j=1,2,\ldots,l.$ Now, assume that $\gcd (a,b)=1$ , we put for example, $c= b_1^{\beta_1} a_2^{\alpha_2}\cdots p_k^{\alpha_k}$ and, $d=a_1^{\alpha_1}b_2^{\beta_2}\cdots b_l^{\beta_l}.$ Now, you can see that, $ab=cd$ and $\gcd(a,b)=\gcd(c,d)=1$ and $a,b,c,d \neq 1$ , but $a ,b\notin \{ c,d\}.$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a