Unsolved Great Common Divisor and Divisibility Problem

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

Problem 1

If NN and MM are natural number such that NM=112+1314+12016+12017\frac{N}{M} = 1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4}+ \cdots - \frac{1}{2016} + \frac{1}{2017} Prove that 759759 divides NN.

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

Problem 2

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

I get a=(20170)+2(20172)+4(20174)+6(20176)++2014(20172014)+2016(20172016)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=(20171)+2(20173)+4(20175)+6(20177)++2014(20172015)+2016(20172017)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
2 years, 4 months ago

No vote yet
1 vote

  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:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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 33 (in this case, 36=7293^6 = 729), write NM\dfrac{N}{M} as 172911458+A243B \frac1{729} - \frac1{1458} + \frac{A}{243B} where AA and BB are integers and 3B.3 \nmid B. After getting a common denominator, this becomes B+6A1458B \frac{B+6A}{1458B} so the numerator is not divisible by 3.

This pretty clearly generalizes to any other alternating harmonic number.

Patrick Corn - 2 years, 3 months ago

Log in to reply

What have you tried?

Calvin Lin Staff - 2 years, 4 months ago

Log in to reply

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

Jason Chrysoprase - 2 years, 4 months ago

Log in to reply

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

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

Calvin Lin Staff - 2 years, 4 months ago

Log in to reply

@Calvin Lin

  1. It's obvious that 759M759 \mid M. Let a=lcm(1,2,3,...,2017)a = \mathrm{lcm}(1,2,3,...,2017). Since 112+1314+12016+120171 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4}+ \cdots - \frac{1}{2016} + \frac{1}{2017} can be expressed as n=12017(1)n+1ana\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 NN. Wait, isn't n=12017(1)n+1ana\large \frac{\sum_{n=1}^{2017} (-1)^{n+1} \frac{a}{n}}{a} gives us the most simplified expression ? aa it self is in form of MM which is divisible by 759759, and the problem state that NN is divisible by 759759. But then we can cancel out 759759 and hence n=12017(1)n+1ana\large \frac{\sum_{n=1}^{2017} (-1)^{n+1} \frac{a}{n}}{a} is not the most simplified fraction in form of NM\frac{N}{M}, which is a contradiction. Also i do check for the exact value of MM and NN for the most simplified NM\frac{N}{M} on wolfram alpha and 759759 did not divides NN. But i still wonder, since NN is divisible by some prime number greater than 20172017, can we find the prime number ?

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

Jason Chrysoprase - 2 years, 4 months ago

Log in to reply

@Jason Chrysoprase

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

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

Calvin Lin Staff - 2 years, 4 months ago

Log in to reply

@Calvin Lin

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

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

Jason Chrysoprase - 2 years, 4 months ago

Log in to reply

@Jason Chrysoprase

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

  2. Great.

Calvin Lin Staff - 2 years, 3 months ago

Log in to reply

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

SKYE RZYM - 2 years, 4 months ago

Log in to reply

A minor comment:

It's actually a=k=01008(20172k)2ka=\sum\limits_{k=0}^{1008}\dbinom {2017}{2k}2^k, not a=(20170)+k=11008(20172k)2ka=\dbinom{2017}0+\sum\limits_{k=1}^{1008}\dbinom{2017}{2k}2k

Similar comment for bb.

Prasun Biswas - 2 years, 3 months ago

Log in to reply

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

Then

An=12((12)n+(1+2)n)Bn=122((1+2)n(12)n)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

An+1=2An+An1,A0=A1=1Bn+1=2Bn+Bn1,B0=0, B1=1A_{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(An,Bn)=1\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

Julian Poon - 2 years, 3 months ago

Log in to reply

A comment regarding your work:

The actual recurrence relation is that An+1=An+2BnA_{n+1}=A_n+2B_n and Bn+1=An+BnB_{n+1}=A_n+B_n from which it follows that An+1=1×Bn+1+BnA_{n+1}=1\times B_{n+1}+B_n. Then notice that we have,

An+1=1×Bn+1+BnBn+1=1×Bn+AnA_{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,ab)\gcd(a,b)=\gcd(b,a-b), we have,

gcd(An+1,Bn+1)=gcd(Bn+1,Bn)=gcd(An+Bn,Bn)=gcd(Bn,An)=gcd(An,Bn)  n1\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(An,Bn)=gcd(An1,Bn1)==gcd(A1,B1)=1\gcd(A_n,B_n)=\gcd(A_{n-1},B_{n-1})=\cdots =\gcd(A_1,B_1)=1.

Prasun Biswas - 2 years, 3 months ago

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

Calvin Lin Staff - 2 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...