Hilbert's 10th was: How do you find the integer solutions (= "Diophantine") to multivariate polynomials. Matiyasevic et al showed that, in general, you can't. The problem is Turing complete. For example, somebody constructed a polynomial in n, p, and a couple of dozen auxiliary variables that can only vanish when p is the nth prime! Matiyasevic once sent me a book. (Soviet era, incredibly cheaply made.) Insensitive to what must have been his austere economic situation, I sent him several packets of Pop Rocks. I addressed the envelope in Cyrillic, and John McCarthy impishly had me append "имени Ке́ренский" to the name of the research facility. Kerensky was much despised in Soviet propaganda. I think the book was one about hypergeometric identities. One such, written with binomial coefficients, mentioned "Moriarty" in cyrillic. I hit the ceiling, thinking that the Russians had fallen for some prank, based on the Sherlock Holmes quote, "At the age of twenty-one, he wrote a treatise upon the binomial theorem <https://en.wikipedia.org/wiki/Binomial_theorem>, which has had a European vogue." I sent a xerox to Martin Gardner, who sent it to the Baker Street Irregulars, who sent it to the CIA. But the hoax was on me. One Harold Davis discovered the theorem, and playfully named it Moriarty's. https://en.wikipedia.org/wiki/A_Treatise_on_the_Binomial_Theorem Had my Russian been better, I'd've noticed that "Дэвиса" was not a "device", but rather how they spell "Davis". --rwg ---------- Forwarded message ---------- From: Warren D Smith <warren.wds@gmail.com> Date: Wed, Jun 7, 2017 at 4:04 PM Subject: Fibonacci divisibility To: billgosper@gmail.com, marniekanarek@gmail.com The fact that GCD[Fibonacci[a], Fibonacci[b]] == Fibonacci[GCD[a, b]], is proven as lemma 4 on p.221 in John H. Halton: ON THE DIVISIBILITY PROPERTIES OF FIBONACCI NUMBERS (1966) http://www.fq.math.ca/Scanned/4-3/halton.pdf Halton also in lemma 5 says F_m is divisible by F_n , if and only if either m is divisible by n, or n = 2. Divisibility properties like these were a key ingredient of the famous proof by Julia Robinson et al, that established the undecidability of diophantine equation solving. Robinson et al had everything they needed except for this missing ingredient, which was found by Yuri Matiyasevich thus competing the proof in 1970. However, it would seem Robinson et al could have avoided the need for Matiyasevic if they had bothered to read this 1966 paper by Halton? See https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem