★ CODING ★ AMSTRAD ACTION DISCOURSE - FERMAT'S ALGORITHM TO FIND A PRIME FACTOR OF A NUMBER|Amstrad Action) ★ |
| Amstrad Action Discourse - Fermat's Algorithm to Find a Prime Factor of a Number |
If CPC techie-talk is all Greek to you, let JAMES WILSON, in the second of this series, demonstrate why. Euclid's Algorithm brings to light a remarkable property of the Highest Common Factor (HCF) which is not obvious if the H.C.F. is determined by factorisation into primes. This property is that the highest common factor, h, of two natural numbers a and b is representable as the difference between a multiple of a and a multiple of b, that is h = ax - bywhere x and y are natural numbers.One reason why this property is so interesting is that equations of this form were extensively studied by Diophantus (ca. 180 AD), probably the best, ancient algebraist, and are today often referred to as Diophantine Equations. The only known woman mathematician of the ancient Alexandrian school, Hypatia, recognised this (alas, she was battered to death by Christian fanatics in about 415 AD). Diophantus was the first to employ signs (for positive and negative) systematically and he also used symbols for unknowns, powers and so on He solved linear, quadratic and at least one cubic equation. In some of his methods he effectively used the device of approximating to limits, a method eventually systematized by Sir Issac Newton in the 1670's as Calculus. Using his limit technique, Diophantus attempted to divide 13 into two square numbers, each of which is to be greater than 6. He arrived at squares with sides of 258/101 and 257/101. Clearly, in all these matters, the knowledge as to whether any given number is prime (that is. divisible by only itself and 1) or not is of utmost importance. If any number is not divisible by any prime number in the range 2 up to its square root then that number itself must be prime. The process of checking the divisibility of a number by the primes is very laborious and many mathematicians have developed methods to reduce this labour. Gauss (1777-1855) and Pierre Format (1601-1665) were quite successful and Fermat's method, which is extremely simple in principle, is explained below. Let P be the number we wish to test and let n be the lowest number such that n2 > P. All we have to do now is form the series of numbers n2 - P , ( n + 1) 2 - P , ( n + 2 ) 2 - P ...If a number is reached which is a perfect square then we havex2 - p = y2 and thus P = X2 - Y2 = (X = y);If P is prime then the solution we reach gives x + y-Pand x - y = 1.The difference between each term of the series is 2n = m wherein is 1,3.5.... as the algorithm progresses. An example illustrates this best. Let P = 9271. This lies between 962 and 972 , so that n = 97. Our series is thus n2 — P 972 - 9271 = 9409 - 9271 = 138but 729 is the perfect square of 27, thus we have x2 - 9271 = 729. Therefore x=100 and, from above , P = (x + y)(x - y) , 9271 = 123 x 73. |
|  |
 | Page précédente : Amstrad Action Discourse - Euclid's Algorith to Calculate the H.C.F of Two Numbers |  |
|
