Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2006-11-17, 00:41   #1
dsouza123's Avatar
Sep 2002

2·331 Posts
Default 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 ?
dsouza123 is offline   Reply With Quote
Old 2006-11-17, 17:04   #2
ewmayer's Avatar
Sep 2002
Rep├║blica de California

266348 Posts

Originally Posted by dsouza123 View Post
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.)
ewmayer is offline   Reply With Quote
Old 2006-11-17, 17:07   #3
dsouza123's Avatar
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 ?
dsouza123 is offline   Reply With Quote
Old 2006-11-17, 18:06   #4
dsouza123's Avatar
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 ?
dsouza123 is offline   Reply With Quote
Old 2006-11-18, 11:52   #5
retina's Avatar
"The unspeakable one"
Jun 2006
My evil lair

142368 Posts
Default 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
retina is online now   Reply With Quote
Old 2006-11-18, 12:57   #6
akruppa's Avatar
Aug 2002

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.

akruppa is offline   Reply With Quote
Old 2006-11-18, 16:10   #7
dsouza123's Avatar
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.

The unequal positive integers 6, 30 have as the first the integer coordinates (1,5) so 6 * 5 = 30.
dsouza123 is offline   Reply With Quote

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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.