2002 Czech-Polish-Slovak
- zadid xcalibured
- Posts:217
- Joined:Thu Oct 27, 2011 11:04 am
- Location:mymensingh
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
- Location:Khulna,Bangladesh.
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!
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!
বড় ভালবাসি তোমায়,মা
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!}}$
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.
$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
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
- zadid xcalibured
- Posts:217
- Joined:Thu Oct 27, 2011 11:04 am
- Location:mymensingh
Re: 2002 Czech-Polish-Slovak
I wish people started posting cool medium level number theory problems like this.