×

# Unsolved Great Common Divisor and Divisibility Problem

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.

Note by Jason Chrysoprase
9 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> 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"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

There must be some mistake in problem 1. I'm pretty sure that the numerators of the alternating harmonic numbers are never divisible 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.

- 8 months, 4 weeks ago

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

- 8 months, 3 weeks ago

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$$.

- 8 months, 3 weeks ago

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 :)

Staff - 8 months, 3 weeks ago

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$$.

- 8 months, 4 weeks ago

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, ...

- 9 months ago

Staff - 9 months ago

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 ?

- 9 months ago

1. Work on understanding $$M$$ in many different ways. For example, can $$759 \mid M$$? Why, or why not?

2. 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$$.

Staff - 9 months ago

1. It's obvious that $$759 \mid M$$. Let $$a = \mathrm{lcm}(1,2,3,...,2017)$$. Since $$1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4}+ \cdots - \frac{1}{2016} + \frac{1}{2017}$$ can be expressed as $$\large \frac{\sum_{n=1}^{2017} (-1)^{n+1} \frac{a}{n}}{a}$$ with positive integer numerator and denominator. How does that will help solving for $$N$$. Wait, isn't $$\large \frac{\sum_{n=1}^{2017} (-1)^{n+1} \frac{a}{n}}{a}$$ gives us the most simplified expression ? $$a$$ it self is in form of $$M$$ which is divisible by $$759$$, and the problem state that $$N$$ is divisible by $$759$$. But then we can cancel out $$759$$ and hence $$\large \frac{\sum_{n=1}^{2017} (-1)^{n+1} \frac{a}{n}}{a}$$ is not the most simplified fraction in form of $$\frac{N}{M}$$, which is a contradiction. Also i do check for the exact value of $$M$$ and $$N$$ for the most simplified $$\frac{N}{M}$$ on wolfram alpha and $$759$$ did not divides $$N$$. But i still wonder, since $$N$$ is divisible by some prime number greater than $$2017$$, can we find the prime number ?

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

- 9 months ago

1. Great, so you realize that in the naive / unsimplified numerator, we must have $$759^2 \mid N'$$. However, $$N'$$ still isn't a very nice number to manipulate. What can we do with it?

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

Staff - 9 months ago

1. I don't understand your statement. Since for the most simplified $$\frac{N}{M}$$, $$N$$ is not divisible by $$759$$, it should be divisible by some prime number greater than $$2017$$. Then for non simplified $$\frac{N}{M}$$, we can just multiply $$759$$ on numerator and denominator. Isn't it that easy ? I'm super confused. Shouldn't the problem itself was wrong ?

2. 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$$

- 9 months ago

1. When I said "simplified", I did not mean "in reduced form". Currently, the values $$\frac{ N} { M }$$ are not easily understood. In particular, you want to claim that $$M = lcm(\ldots )$$, but if the problem statement is true, then that can't be since $$759 \mid M$$. So, let's choose an equivalent form $$\frac{N}{M} = \frac{ A}{B}$$ that is not completely reduced, where $$A$$ and $$B$$ are easy for us to calculate and understand. The choice of $$B = \lcm ( \ldots )$$ doesn't work, so what potential (naive) forms can we try? The goal here is to show that (say) $$759 ^3 \not \mid B$$ and $$759 ^3 \mid A$$, from which we can conclude that $$759 \mid N$$.

2. Great.

Staff - 9 months ago