Japan-2012-3(BOMC-2)

Discussion on Bangladesh National Math Camp
User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.
Japan-2012-3(BOMC-2)

Unread post by Tahmid Hasan » Thu Mar 29, 2012 10:34 pm

Let $p$ be prime.Find all possible integers $n$ such that for all integers $x$,if $x^n-1$ is divisible by $p$,then $x^n-1$ is divisible by $p^2$ as well.
বড় ভালবাসি তোমায়,মা

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

Re: Japan-2012-3(BOMC-2)

Unread post by *Mahi* » Fri Mar 30, 2012 2:04 am

Direct LTE:
With $x$ s.t. $p||x-1$
$v_p(x^n-1)=v_p(x-1)+v_p(n)$ , which is greater than $2$ if and only if $v_p(n) \geq 1$.
In reverse, if $p \not | n$ then with $x$ s.t. $p||x-1$,
$v_p(x^n-1)=v_p(x-1)+v_p(n)=1+0=1$, which means $p|x^n-1$ but $p^2 \not | x^n-1$.
So answer is $n=mp$ for some $m \in \mathbb N_0$
Again, if $p | x^{pm}-1$ then $x^{pm}-1 = (x^m-1)((x^m)^{p-1}+(x^m)^{p-2}+(x^m)^{p-3})+\cdots +1 \equiv p(x^m-1)(\text{mod p)}$
As $x^{pm} \equiv (x^p)^m \equiv x^m \equiv 1 \text{(mod p)}$
So , $p^2|x^{pm}-1$
Please read Forum Guide and Rules before you post.

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

Nur Muhammad Shafiullah | Mahi

Post Reply