13 -11

For discussing Olympiad Level Number Theory problems
samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm
13 -11

Unread post by samiul_samin » Thu Feb 15, 2018 10:28 am

$N$ is a positive integer. If $11N$ divides ($13^N-1$)then, what is the minimum
value of $N$?

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: 13 -11

Unread post by samiul_samin » Thu Feb 15, 2018 10:29 am

Anyone please give any hint at least.

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: 13 -11

Unread post by ahmedittihad » Sun Feb 18, 2018 8:07 am

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.
Frankly, my dear, I don't give a damn.

User avatar
Tasnood
Posts:73
Joined:Tue Jan 06, 2015 1:46 pm

Re: 13 -11

Unread post by Tasnood » 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 :oops:

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: 13 -11

Unread post by samiul_samin » Sun Feb 18, 2018 10:58 am

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 :oops:
How can I get mod $11N$?

User avatar
Tasnood
Posts:73
Joined:Tue Jan 06, 2015 1:46 pm

Re: 13 -11

Unread post by Tasnood » Sun Feb 18, 2018 11:00 am

:oops: I missed the middle stamp!
However a simple change will make the solution correct.
Last edited by Tasnood on Sun Feb 18, 2018 11:05 am, edited 1 time in total.

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: 13 -11

Unread post by samiul_samin » Sun Feb 18, 2018 11:01 am

Tasnood wrote:
Sun Feb 18, 2018 11:00 am
:oops: I missed the middle stamp!
No problem.I am also trying it.

Post Reply