## 2002 Czech-Polish-Slovak

For discussing Olympiad Level Number Theory problems
Posts: 217
Joined: Thu Oct 27, 2011 11:04 am
Location: mymensingh

### 2002 Czech-Polish-Slovak

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.

Tahmid Hasan
Posts: 665
Joined: Thu Dec 09, 2010 5:34 pm

### Re: 2002 Czech-Polish-Slovak

$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!
বড় ভালবাসি তোমায়,মা

SANZEED
Posts: 550
Joined: Wed Dec 28, 2011 6:45 pm

### Re: 2002 Czech-Polish-Slovak

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

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

### Re: 2002 Czech-Polish-Slovak

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.
Use $L^AT_EX$, It makes our work a lot easier!