2002 Czech-Polish-Slovak

For discussing Olympiad Level Number Theory problems
User avatar
zadid xcalibured
Posts:217
Joined:Thu Oct 27, 2011 11:04 am
Location:mymensingh
2002 Czech-Polish-Slovak

Unread post by zadid xcalibured » Sat Apr 13, 2013 9:54 pm

Let $n$ and $p$ be integers such that $n>1$ and $p$ be a prime.If $n|p-1$ and $p|n^3-1$,show that $4p-3$ is a perfect square.

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: 2002 Czech-Polish-Slovak

Unread post by Tahmid Hasan » Sat Apr 13, 2013 11:40 pm

$n|p-1 \Rightarrow n \le p-1 \Rightarrow n-1 \le p-2<p \Rightarrow p \nmid n-1$.
Hence $p|n^3-1 \Rightarrow p|n^2+n+1$.
Let $n^2+n+1=pk[k \in \mathbb{N}] \Rightarrow n|pk-1=k(p-1)+k-1 \Rightarrow n|k-1$.
Let $k-1=nt[t \in \mathbb{N}_0]$.
So $n^2+n+1=p(nt+1) \Rightarrow n(n+1-pt)=p-1 \Rightarrow n+1-pt \ge 0 \Rightarrow pt \le n+1$.
Again $n \le p-1 \Rightarrow n+1 \le p$.
Hence $pt \le n+1 \le p$. So $t=0,1$.
$t=1 \Rightarrow n+1=p$. So $p|n^2+n+1-n(n+1)=1$, a contradiction.
$t=0 \Rightarrow k=1 \Rightarrow p=n^2+n+1 \Rightarrow 4p-3=(2n+1)^2$, done!
বড় ভালবাসি তোমায়,মা

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: 2002 Czech-Polish-Slovak

Unread post by SANZEED » Sat Apr 13, 2013 11:59 pm

My solution's quite the same. :twisted:
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: 2002 Czech-Polish-Slovak

Unread post by *Mahi* » Sun Apr 14, 2013 10:17 am

Basic modular arithmetics.
$n \mid p-1 \Rightarrow p -1 = nk \Rightarrow p = nk+1, k \ge 1$
$0 \equiv n^3-1 \equiv (n-1)(n^2+n+1) \pmod {nk+1}$
$\equiv n^2+n+1\equiv 0 \pmod {nk+1}$ as $p = nk+1 > n-1$
$\Rightarrow n^2+n+1 \equiv nk+1 \pmod {nk+1}$
$\Rightarrow n(n+1) \equiv nk \pmod {nk+1}$
$\Rightarrow n+1 \equiv k \pmod {nk+1}$...(i) as $(n,nk+1) = 1$
As both $n+1, k \le nk+1$, (i) implies $n+1=k$.
So, $p = nk+1 = n(n+1) +1 = n^2+n+1$, and the rest follows.
Last edited by Phlembac Adib Hasan on Sun Apr 14, 2013 12:32 pm, edited 1 time in total.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
zadid xcalibured
Posts:217
Joined:Thu Oct 27, 2011 11:04 am
Location:mymensingh

Re: 2002 Czech-Polish-Slovak

Unread post by zadid xcalibured » Sun Apr 14, 2013 11:26 pm

I wish people started posting cool medium level number theory problems like this. :mrgreen: :mrgreen: :mrgreen:

Post Reply