mersenneforum.org > Math Methods to determine integer multiples
 Register FAQ Search Today's Posts Mark Forums Read

 2006-11-17, 00:41 #1 dsouza123     Sep 2002 2·331 Posts Methods to determine integer multiples Given two positive integers, each greater than one, what mathematical methods can determine if one is a multiple of the other ? Some methods : Integer division, if the remainder is zero. (If the integers are different the larger is divided by the smaller.) The antilog of the subtraction of the logs of the two numbers. If it is an integer then it is a case of a multiple. GCD, a multiple if the result is one of the numbers. Repeated subtraction (smaller from larger, if not originally equal) until the result is less than the smaller, if zero then a multiple. What other mathematical methods exist ?
2006-11-17, 17:04   #2
ewmayer
2ω=0

Sep 2002
República de California

266348 Posts

Quote:
 Originally Posted by dsouza123 What other mathematical methods exist ?
How many more do you really need?

From an algorithmic standpoint, a more interesting question at this point is: what is the asymptotic worst-case complexity of the above methods? (Hint: homework assignment.)

 2006-11-17, 17:07 #3 dsouza123     Sep 2002 2×331 Posts A slight variation on one of the previous methods, Repeated addition (if the numbers weren't the same) of the smaller until it is equal or exceeds the larger. How, if applicable, can modular arithmetic, linear algebra, modular inverses, discrete logarithms, the chinese remainder theorem, geometry, algebra or other topics/fields of mathematics be used to determine if the integers in question are multiples ?
 2006-11-17, 18:06 #4 dsouza123     Sep 2002 2·331 Posts Not really need, but I would like to know and understand to some degree, how various methods or branches of math can be used to solve the same problem, in this case determining if a given pair of postive integers are integer multiples. I realize that subtraction and addition would be extremely slow methods just by thinking how many times it would have to be done to get an answer unless the numbers are within some small factor, say 1000 times the value, of the larger to the smaller. How would I determine the worst case (or any case) complexity of them ? Write test programs and time them ? What is used to find this out ? Not in the sense of using google to search but the topic or field of research that is involved. Is it some branch of mathematics or computer science ?
 2006-11-18, 11:52 #5 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 142368 Posts One more Integer multiplication of the smaller number by successive integers > 0 until the result either equals the larger number or exceeds the larger number. Last fiddled with by retina on 2006-11-18 at 11:54 Reason: typos
 2006-11-18, 12:57 #6 akruppa     "Nancy" Aug 2002 Alexandria 9A316 Posts If efficiency is not a concern, completely factor into primes both numbers and check if all primes and prime powers in the factorisation of one number also appear in the factorisation of the other. Alex
 2006-11-18, 16:10 #7 dsouza123     Sep 2002 29616 Posts A method using an x y graph, ie using analytic geometry. Only if x and y are different. Plot the line with coordinates (0,0) and (x,y) with x and y the two postitive integers with x the smaller and y the larger. Ignoring (0,0) if the only pair of integer coordinates on this line are at (x,y) then they are not multiples. If there is more than one pair of coordinates then at (1,?) ? is the multiple of x when multiplied together is y. Example The unequal positive integers 6, 30 have as the first the integer coordinates (1,5) so 6 * 5 = 30.

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Math 16 2017-03-01 07:17 fenderbender Math 14 2007-07-28 23:24 hyderman Homework Help 7 2007-06-17 06:01 wblipp GMP-ECM 1 2005-04-19 15:58 Boulder Software 2 2003-08-20 11:55

All times are UTC. The time now is 13:05.

Tue Dec 7 13:05:19 UTC 2021 up 137 days, 7:34, 0 users, load averages: 1.55, 1.53, 1.62