$N$ is a positive integer. If $11N$ divides ($13^N-1$)then, what is the minimum
value of $N$?
13 -11
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
Re: 13 -11
Anyone please give any hint at least.
- ahmedittihad
- Posts:181
- Joined:Mon Mar 28, 2016 6:21 pm
Re: 13 -11
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.
2. Here's the hint, Use fermat's little theorem.
Frankly, my dear, I don't give a damn.
Re: 13 -11
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
$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
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
Re: 13 -11
How can I get mod $11N$?Tasnood wrote: ↑Sun Feb 18, 2018 10:08 amEasy 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
I missed the middle stamp!
However a simple change will make the solution correct.
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.
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm