| [ QuizWit ] in KIDS 글 쓴 이(By): lontano (lontano) 날 짜 (Date): 2006년 2월 2일 목요일 오전 07시 40분 36초 제 목(Title): Re: 피보나치 수열에서 > gcd(f_n,f_m) = f_gcd(m,n) > 근데 이런 성질의 수열이 또 있나요? 있다고 합니다. f(1) = 1, f(2) = 2, f(n) = f(n-2) + 2 f(n-1) 이 수열 역시 gcd(f(n),f(m)) = f(gcd(n,m))을 만족한다는군요. 증명은 피보나치 수열의 경우와 같은 방법으로 된다고 합니다. http://www.mathreference.com/num-deq,fib.html gcd와 commute하는 수열을 만드는 일반적인 방법도 제시되었다는군요. 저는 머리가 나빠서 읽어도 전혀 이해가 안 됩니다만... http://www.csulb.edu/~rmena/fibpape_final_version.pdf 또는 http://www.findarticles.com/p/articles/mi_qa3789/is_200306/ai_n9251638/pg_4 에서 Holzsager로 검색. 이런 것도 있군요. Knuth's GCD Lemma: gcd(2^p - 1, 2^q - 1) = 2^gcd(p,q) - 1 http://mathworld.wolfram.com/GreatestCommonDivisor.html http://www.garlic.com/~wedgingt/mersenne.html |