I'm having a hard time with this problem. Need help.

Problem 1

If \(N\) and \(M\) are natural number such that \[\frac{N}{M} = 1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4}+ \cdots - \frac{1}{2016} + \frac{1}{2017}\] Prove that \(759\) divides \(N\).

I don't even have an idea where to begin. I'm stuck at the problem.

Problem 2

If \(a\) and \(b\) are natural number such that \(a+b\sqrt{2} = (1+\sqrt{2})^{2017}\). Prove that \(\gcd(a,b) = 1\).

I get \(a = \binom{2017}{0} + 2 \binom{2017}{2} + 4\binom{2017}{4} + 6\binom{2017}{6} + \cdots + 2014 \binom{2017}{2014}+ 2016\binom{2017}{2016}\) and \(b=\binom{2017}{1} + 2 \binom{2017}{3} + 4\binom{2017}{5} + 6\binom{2017}{7} + \cdots + 2014 \binom{2017}{2015}+ 2016\binom{2017}{2017}\). Then i don't know what to do.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestThere must be some mistake in problem 1. I'm pretty sure that the numerators of the alternating harmonic numbers are

neverdivisible by 3, let alone 759. For this particular one, the argument is: after taking out the two terms with denominators divisible by the maximal possible power of \(3\) (in this case, \(3^6 = 729\)), write \(\dfrac{N}{M}\) as \[ \frac1{729} - \frac1{1458} + \frac{A}{243B} \] where \(A\) and \(B\) are integers and \(3 \nmid B.\) After getting a common denominator, this becomes \[ \frac{B+6A}{1458B} \] so the numerator is not divisible by 3.This pretty clearly generalizes to any other alternating harmonic number.

Log in to reply

Problem 2: Potential method Let \(\left(1+\sqrt{2}\right)^n=A_n+B_n\sqrt{2}\).

Then

\[A_n = \frac{1}{2}\left(\left(1-\sqrt{2}\right)^n+\left(1+\sqrt{2}\right)^n\right) \\ B_n = \frac{1}{2\sqrt{2}}\left(\left(1+\sqrt{2}\right)^n-\left(1-\sqrt{2}\right)^n\right)\]

It follows from this that

\[A_{n+1}=2A_n+A_{n-1}, \quad A_0=A_1=1 \\ B_{n+1}=2B_n+B_{n-1}, \quad B_0=0,\ B_1=1\]

Then what is left is to proof that \(\gcd \left(A_n,B_n\right)=1\), which appears to be the case but I haven't found one yet.

EDIT: I've read the rest of the comments. This solution is kinda dumb

Log in to reply

A comment regarding your work:

The actual recurrence relation is that \(A_{n+1}=A_n+2B_n\) and \(B_{n+1}=A_n+B_n\) from which it follows that \(A_{n+1}=1\times B_{n+1}+B_n\). Then notice that we have,

\[A_{n+1}=1\times B_{n+1}+B_n\\ B_{n+1}=1\times B_n+A_n\]

From the above, we note that since \(\gcd(a,b)=\gcd(b,a-b)\), we have,

\[\gcd(A_{n+1},B_{n+1})=\gcd(B_{n+1},B_n)=\gcd(A_n+B_n,B_n)=\gcd(B_n,A_n)=\gcd(A_n,B_n)~\forall~n\geq 1\]

Hence, we conclude that \(\gcd(A_n,B_n)=\gcd(A_{n-1},B_{n-1})=\cdots =\gcd(A_1,B_1)=1\).

Log in to reply

Very nicely done!

That's one reason why it's hard to definitely conclude "this particular approach will yield no result". I agree that it looks slightly unapproachable at first, and am pleasantly amazed by what @Prasun Biswas has done :)

Log in to reply

A minor comment:

It's actually \(a=\sum\limits_{k=0}^{1008}\dbinom {2017}{2k}2^k\),

not\(a=\dbinom{2017}0+\sum\limits_{k=1}^{1008}\dbinom{2017}{2k}2k\)Similar comment for \(b\).

Log in to reply

For problem 3 Try to substitute \(n\) with \(n=2k\) or \(n=2k+1\). And then, find out when k is congruent 0 mod 10, congruent 1 mod 10, ...

Log in to reply

What have you tried?

Log in to reply

I have told everything i tried. I have no idea about problem 1. I have solved for \(a\) and \(b\) for problem 2, but i don't know how to find their gcd. I know that \(\frac{n(n+1)}{2} = 1+2+3+\cdots+n\), what do i do next ?

Log in to reply

Work on undersatnding \(a, b \) in many different ways. The current way that you have doesn't allow for easy manipulation. Is there another relationship that exists between \(a\) and \(b\) directly? E.g. if we can show that \( 2017 a + 7102 b = 1 \), then it follows that \( \gcd(a,b) = 1 \).

Log in to reply

I'm not quite sure for this moment. Any more hints ?

Log in to reply

Hint: \( x^2 - y^2 = (x-y)(x+y) \).

Log in to reply

So since \((1+\sqrt{2})^{2017} = a+b \sqrt{2}\) and \((1-\sqrt{2})^{2017} = a-b\sqrt{2}\), multiply both equation gives us \(\left((1+\sqrt{2})(1-\sqrt{2})\right)^{2017}=(a+b \sqrt{2})(a-b \sqrt{2})\). Hence \((-1)^{2017}=-1=a^2 - 2b^2\). So \(2b^2 = a^2(1) + 1\). By Euclidean Algorithm, \(a^2 = 1(a^2) + 0\). Hence their great common divisor is equal \(1\)

Log in to reply

Great.

Log in to reply