gcd(a2m+1,a2n+1)={1 if a is even2 if a is odd\gcd(a^{2^{m}}+1,a^{2^{n}}+1 )=\begin{cases} 1 \text{ if }a \text { is even} \\ 2 \text{ if }a \text { is odd} \end{cases}gcd(a2m+1,a2n+1)={1 if a is even2 if a is odd
If m≠nm \neq nm=n, prove the equation above.
Note by Akshat Sharda 5 years, 3 months ago
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
_italics_
**bold**
__bold__
- bulleted- list
1. numbered2. list
paragraph 1paragraph 2
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"
\(
\)
\[
\]
2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Note that a2m+1−1=(a2m−1)(a2m+1)a^{2^{m+1}} - 1 = (a^{2^m} - 1)(a^{2^m} + 1)a2m+1−1=(a2m−1)(a2m+1). Thus, if n>mn > mn>m, then a2n−1=(a2m−1)(a2m+1)(a2m+1+1)…(a2n−1+1)a^{2^n} - 1 = (a^{2^m} - 1)(a^{2^m} + 1)(a^{2^{m+1}} + 1) \ldots (a^{2^{n-1}} + 1)a2n−1=(a2m−1)(a2m+1)(a2m+1+1)…(a2n−1+1). Thus a2n+1=(a2m+1)⋅k+2a^{2^n} + 1 = (a^{2^m} + 1) \cdot k + 2a2n+1=(a2m+1)⋅k+2 for some integer kkk. We know that gcd(a,b+ka)=gcd(a,b)\gcd(a, b+ka) = \gcd(a, b)gcd(a,b+ka)=gcd(a,b), thus gcd(a2m+1,a2n+1)=gcd(a2m+1,2)\gcd(a^{2^m} + 1, a^{2^n} + 1) = \gcd(a^{2^m} + 1, 2)gcd(a2m+1,a2n+1)=gcd(a2m+1,2). If aaa is odd, clearly a2m+1a^{2^m} + 1a2m+1 is even, so the GCD is 2. If aaa is even, clearly a2m+1a^{2^m} + 1a2m+1 is odd, so 2 doesn't divide it, thus the only remaining choice is that the GCD is 1.
Log in to reply
Aah! Thanks!
Was this your original ? Nice one @Ivan Koswara !!!
@A Former Brilliant Member – No :-P if it would have been why would I write need help
@Akshat Sharda – to prove it :P
I had a new Idea !!!
Let us research some properties of gcd of two towers leaving same remainder modulo some number
@Akshat Sharda
I can't understand what you're saying! :-) But let's discuss... Are you making another note? @Chinmay Sangawadekar
wait I will create a note , can you come on slack now ?
Problem Loading...
Note Loading...
Set Loading...
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
Note that a2m+1−1=(a2m−1)(a2m+1). Thus, if n>m, then a2n−1=(a2m−1)(a2m+1)(a2m+1+1)…(a2n−1+1). Thus a2n+1=(a2m+1)⋅k+2 for some integer k. We know that gcd(a,b+ka)=gcd(a,b), thus gcd(a2m+1,a2n+1)=gcd(a2m+1,2). If a is odd, clearly a2m+1 is even, so the GCD is 2. If a is even, clearly a2m+1 is odd, so 2 doesn't divide it, thus the only remaining choice is that the GCD is 1.
Log in to reply
Aah! Thanks!
Log in to reply
Was this your original ? Nice one @Ivan Koswara !!!
Log in to reply
No :-P if it would have been why would I write need help
Log in to reply
to prove it :P
I had a new Idea !!!
Let us research some properties of gcd of two towers leaving same remainder modulo some number
@Akshat Sharda
Log in to reply
I can't understand what you're saying! :-) But let's discuss... Are you making another note? @Chinmay Sangawadekar
Log in to reply
wait I will create a note , can you come on slack now ?