Methods to determine integer multiples

dsouza123 · 2006-11-17, 00:41

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 ?

ewmayer · 2006-11-17, 17:04

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.)

dsouza123 · 2006-11-17, 17:07

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 ?

dsouza123 · 2006-11-17, 18:06

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 ?

retina · 2006-11-18, 11:52

Integer multiplication of the smaller number by successive integers > 0 until the result either equals the larger number or exceeds the larger number.

akruppa · 2006-11-18, 12:57

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

dsouza123 · 2006-11-18, 16:10

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.

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-18, 11:52	#5
retina Undefined "The unspeakable one" Jun 2006 My evil lair 3⁵×5² 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

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	2017-03-01 07:17
Determine squares	fenderbender	Math	14	2007-07-28 23:24
determine	hyderman	Homework Help	7	2007-06-17 06:01
Guidelines for ECM Before Other Methods	wblipp	GMP-ECM	1	2005-04-19 15:58
How to determine the P-1 boundaries?	Boulder	Software	2	2003-08-20 11:55

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, 12:57	#6
akruppa "Nancy" Aug 2002 Alexandria 2,467 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 662₁₀ 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.