20061117, 00:41  #1 
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 ? 
20061117, 17:04  #2 
∂^{2}ω=0
Sep 2002
República de California
26634_{8} Posts 

20061117, 17:07  #3 
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 ? 
20061117, 18:06  #4 
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 ? 
20061118, 11:52  #5 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
14236_{8} 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 20061118 at 11:54 Reason: typos 
20061118, 12:57  #6 
"Nancy"
Aug 2002
Alexandria
9A3_{16} 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 
20061118, 16:10  #7 
Sep 2002
296_{16} 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Finding multiples of a real number that are close to a whole number  mickfrancis  Math  16  20170301 07:17 
Determine squares  fenderbender  Math  14  20070728 23:24 
determine  hyderman  Homework Help  7  20070617 06:01 
Guidelines for ECM Before Other Methods  wblipp  GMPECM  1  20050419 15:58 
How to determine the P1 boundaries?  Boulder  Software  2  20030820 11:55 