Page 1 of 1
13 -11
Posted: Thu Feb 15, 2018 10:28 am
by samiul_samin
$N$ is a positive integer. If $11N$ divides ($13^N-1$)then, what is the minimum
value of $N$?
Re: 13 -11
Posted: Thu Feb 15, 2018 10:29 am
by samiul_samin
Anyone please give any hint at least.
Re: 13 -11
Posted: Sun Feb 18, 2018 8:07 am
by ahmedittihad
1. You won't get a hint just after $1$ minute of posting that problem.
2. Here's the hint, Use fermat's little theorem.
Re: 13 -11
Posted: Sun Feb 18, 2018 10:08 am
by Tasnood
Easy to prove by
Modular Arithmetic
$11|13^N-1$ We write:
$13^N-1 \equiv 0 \Rightarrow 13^N \equiv 1 \Rightarrow (11+2)^N \equiv 1$
mod$(11)$
We can write the expression $(11+2)^N=11^N+{{N} \choose {1}} 11^{N-1}.2+{{N} \choose {2}} 11^{N-2}.2^2+...+{{N} \choose {N-1}} 11.2^{N-1}+2^N$
Here, all terms are divisible by $11$ except $2^N$
So, we can write: $2^N \equiv 1$
mod$(11)$.....
(1)
Applying
Fermat's Little Theorem we get:
$2^{10} \equiv 1$
mod$(11)$......
(2)
Applying
GCD Lemma for
(1) and
(2), we get:
$2^{GCD(N,10)} \equiv 1$
mod$(11)$
Assume that,
GCD$(N,10)=d$ Then, $d$ divides $10$. So, $d=2,5,10$
Here,$2^2-1$, $2^5-1$ aren't divisible by $11$
So, $2^10 \equiv 1$
mod$(11)$
Then the minimum value of $N=10$
I think it is the correct answer
Re: 13 -11
Posted: Sun Feb 18, 2018 10:58 am
by samiul_samin
Tasnood wrote: ↑Sun Feb 18, 2018 10:08 am
Easy to prove by
Modular Arithmetic
$11|13^N-1$ We write:
$13^N-1 \equiv 0 \Rightarrow 13^N \equiv 1 \Rightarrow (11+2)^N \equiv 1$
mod$(11)$
We can write the expression $(11+2)^N=11^N+{{N} \choose {1}} 11^{N-1}.2+{{N} \choose {2}} 11^{N-2}.2^2+...+{{N} \choose {N-1}} 11.2^{N-1}+2^N$
Here, all terms are divisible by $11$ except $2^N$
So, we can write: $2^N \equiv 1$
mod$(11)$.....
(1)
Applying
Fermat's Little Theorem we get:
$2^{10} \equiv 1$
mod$(11)$......
(2)
Applying
GCD Lemma for
(1) and
(2), we get:
$2^{GCD(N,10)} \equiv 1$
mod$(11)$
Assume that,
GCD$(N,10)=d$ Then, $d$ divides $10$. So, $d=2,5,10$
Here,$2^2-1$, $2^5-1$ aren't divisible by $11$
So, $2^10 \equiv 1$
mod$(11)$
Then the minimum value of $N=10$
I think it is the correct answer
How can I get
mod $11N$?
Re: 13 -11
Posted: Sun Feb 18, 2018 11:00 am
by Tasnood
I missed the middle stamp!
However a simple change will make the solution correct.
Re: 13 -11
Posted: Sun Feb 18, 2018 11:01 am
by samiul_samin
Tasnood wrote: ↑Sun Feb 18, 2018 11:00 am
I missed the middle stamp!
No problem.I am also trying it.