My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
July 30th, 2009, 11:26 PM   #1
Newbie
 
Joined: Jul 2009

Posts: 1
Thanks: 0

Reverse Modulo

Hi,

I have a little question.
Is there a quick way to evaluate the smallest number (x) that matches the following condition?
x modulo a = e
x modulo b = f
a, b, e and f are given and I want to compute the smallest or if that is not possible any number (x) that matches that condition.

Example:
x modulo 5 = 4
x modulo 7 = 5
The smallest number that matches that condition is 19.
Other values are 54, 89,...

My current solution is working like this
4 5 -> (4 < 5) -> 4+5
9 5 -> (9 > 5) -> 5+7
9 12 -> (9 < 12) -> 9+5
14 12 -> (14 > 12) -> 12+7
14 19 -> (14 < 19) -> 14+5
19 19 -> (19 = 19) -> finished
But that seems kind of slow.
swtrse is offline  
 
August 5th, 2009, 10:12 PM   #2
Newbie
 
Joined: Jul 2009

Posts: 21
Thanks: 0

Re: Reverse Modulo

The problem is you forgot to remove the = when there are over 3 separate numbers in it.
Try dat. <3
Bon Qui Qui is offline  
August 6th, 2009, 04:53 AM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Reverse Modulo

You need Sunzi's theorem (the "Chinese remainder theorem"). I can't tell (!) if that's what you're doing above.

Personally, I use
Code:
chinese(Mod(4, 5), Mod(5, 7))
in Pari.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
modulo, reverse



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
reverse calculation of growth rates outtahere Economics 3 October 3rd, 2013 11:07 AM
reverse engineering a graph ravynware Algebra 0 April 15th, 2012 07:11 PM
reverse n vdrn Number Theory 28 October 22nd, 2011 04:07 PM
Reverse solve f(x)? NumberA Algebra 5 April 19th, 2009 11:03 AM
Reverse calculation Clox Algebra 2 January 23rd, 2008 12:24 AM





Copyright © 2019 My Math Forum. All rights reserved.