Here is an algorithm very simple to find a common factor to a and b.(adsbygoogle = window.adsbygoogle || []).push({});

An example :

a=867

b=1989

1. We compute a'=a mod 10 and b'=b mod 10 so a'=7 b'=9

2. We solve a'x mod 10 = b' (we can use a table)

x=7 7*a'=49=9 mod 10=b'

3. We compute c=x*a=7*867=6069

4. c>b we compute d=(c-a)/10=(6069-1989)/10=4080/10=408

5. If d is even we divide by 2 (because a and b are odd the divisor ins consequently an odd

number) e=d/2=408/2=204 we continue 204/2=102 102/2=51. e=51

6. We try a/e=867/51=17 and b/e=1989/51=39 so 51 divide a and b

7. We continue with new values a and b : a=17 b=39 by apllying the same algo looping from 1.

I gave an example but we have to apply some rules before starting the use of the algo :

If a is even and b odd (or b odd a even or a and b both even) we have to divide a (or b or and b)

by 2 until we reach a and b both odds.

a=1522 b=538

The values a and b will be a=761 b=269 so then we can start applying the algo above.

Each time we reach step 7 we have try dividing a and b by e.

I'm very aware that there is a need to fix some problems to make it working quickly.

So the core of the algo was presented above.

Thank you for any improvement.

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Common factor : new algo?

Loading...

Similar Threads - Common factor algo | Date |
---|---|

Can anyone give a common-sense explanation of singular values? | Dec 10, 2012 |

Looking for a common solution of two systems | Nov 29, 2012 |

Theorem 1.2.1. Common Divisor | Jun 21, 2012 |

How to tell if something has a common factor | Feb 4, 2010 |

Help : greatest common factor | May 30, 2006 |

**Physics Forums - The Fusion of Science and Community**