Wikipedia:Reference desk/Archives/Mathematics/2010 December 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 27

applied mathematical.

Hello:can you help me about applied mathematical:Analithical calculation by means of least squares, with key to the exercises. —Preceding unsigned comment added by 46.19.224.252 (talk) 17:56, 27 December 2010 (UTC)

The Wikipedia article on Least squares is quite technical, so it might not be of much help to you. I assume that you meant analytical calculation, but you will have to tell us what type of question you are trying to answer. The Mathworld explanation might be an easier read if you have not met least squares before. Wikipedia also has articles on Simple linear regression and Ordinary least squares, but neither is an easy read for a beginner. Dbfirs 00:25, 28 December 2010 (UTC)

Euclid's Algorithm Part II

Following on from my question above, I am trying to write a program to write the highest common factor of two natural numbers a, b as a linear combination of a and b. To do this, I need a general form of the coefficients m and n in the equation hcf(a,b)=ma+nb, which I am having a challenging time discovering. Some terminology: given two natural numbers a, b, if it takes k iterations of Euclid's algorithm to find hcf(a,b) then I regard this as taking k-1 steps, eg for 21 and 57, it takes three steps. In all of the following, assume that a>b.

So, when two steps are required, there will be two non-zero remainders -let the remainder of the first iteration of Euclid be p and that of the second be q (and so on for more remainders) - and we will have

$hcf(a,b)=b(1+pq)-a(q)$.

Three steps

$hcf(a,b)=a(1+qr)-b(p+pqr+r)$

Four steps

$hcf(a,b)=b(1+rs+pq+pqrs+ps)-a(q+qrs+s)$

I am having a rather hard time determining the coefficients of a and b when there are k steps. An obvious pattern doesn't immediately jump out at me. Does anyone have any advice or suggestions other than just keep going? Thank you. 92.1.66.162 (talk) 19:35, 27 December 2010 (UTC)

The usual way to do this is to use the Extended Euclidean algorithm. Why do you want to find the general form of the coefficients? -- Meni Rosenfeld (talk) 20:09, 27 December 2010 (UTC)

Well, my program needs to work for a,b requiring a general k number of steps and so I thought the coefficients would be the best way of tackling it but, on reading your post, just being able to get from the nth step to the (n-1)th and then recursing seems like a much better approach. Thank you. 92.1.66.162 (talk) 20:33, 27 December 2010 (UTC)

If you only want the "hcf" (I've always called it the "gcd"), then you only need the remainders, not the quotients. Michael Hardy (talk) 01:18, 31 December 2010 (UTC)