Divisibility

For discussing Olympiad Level Number Theory problems
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
Divisibility

Unread post by tanmoy » Tue Mar 03, 2015 7:15 pm

Let $n\geq 2$ and $k$ be positive integers. Prove that $(n-1)^{2} \mid (n^{k}-1)$ if and only if $(n-1) \mid k$.
"Questions we can't answer are far better than answers we can't question"

Tahmid
Posts:110
Joined:Wed Mar 20, 2013 10:50 pm

Re: Divisibility

Unread post by Tahmid » Tue Mar 03, 2015 7:35 pm

$n^{k}-1=(n-1)(n^{k-1}+n^{k-2}+......+n^{0})$
so, we need to prove that $(n-1)$ divides $(n^{k-1}+n^{k-2}+......+n^{0})$
now,
$n^{k-1}\equiv 1(modn-1)$
$n^{k-2}\equiv 1(modn-1)$
.
.
.
$n^{0}\equiv 1(modn-1)$
so , $(n^{k-1}+n^{k-2}+......+n^{0})\equiv k\equiv 0(modn-1)$

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Divisibility

Unread post by tanmoy » Tue Mar 03, 2015 10:28 pm

Tahmid wrote:$n^{k}-1=(n-1)(n^{k-1}+n^{k-2}+......+n^{0})$
so, we need to prove that $(n-1)$ divides $(n^{k-1}+n^{k-2}+......+n^{0})$
now,
$n^{k-1}\equiv 1(modn-1)$
$n^{k-2}\equiv 1(modn-1)$
.
.
.
$n^{0}\equiv 1(modn-1)$
so , $(n^{k-1}+n^{k-2}+......+n^{0})\equiv k\equiv 0(modn-1)$
Same as my proof. :mrgreen:
"Questions we can't answer are far better than answers we can't question"

Post Reply