
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
June 19th, 2010, 04:52 PM  #1 
Newbie Joined: May 2010 Posts: 4 Thanks: 0  Why primes number when doing modulo?
hi, Why is that when we do x^m + y^n = z^r (mod N1) and x^m + y^n = z^r (mod N2), we get less false positive . What i mean to ask is why this double filtering is better and why is it much better when using prime number and not just any number . What property of prime numbers make then so special to be used with modulo arithmetic. thanks, Nirav 
June 19th, 2010, 05:18 PM  #2 
Senior Member Joined: Apr 2010 Posts: 215 Thanks: 0  Re: Why primes number when doing modulo?
A prime number is coprime with every integer upto itself, except for 1.

June 19th, 2010, 05:43 PM  #3 
Newbie Joined: May 2010 Posts: 4 Thanks: 0  Re: Why primes number when doing modulo?
How does that help ? So what if it is co prime to every other number 
June 19th, 2010, 10:00 PM  #4 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Re: Why primes number when doing modulo?
I'm not sure about this specific problem, but in general, we cannot guarantee that if a*b=0 (mod m), then either a=0 or b=0 (mod m). If m is prime, then this is true. A simple example is 6: 3*2=0 (mod 6), but neither (3 mod 6) nor (2 mod 6) are 0. This has to do with the fact that the set {0...m1} is a field under addition and multiplication mod m, precisely when m is prime. 
June 20th, 2010, 02:53 AM  #5  
Senior Member Joined: Apr 2010 Posts: 215 Thanks: 0  Re: Why primes number when doing modulo? Quote:
ax = b (mod m) This equation has solutions, iff b is a multiple of GCD(a,m). If m is prime, GCD(a,m)=1, thus it has a solution for every (a,b) pair. (because every integer is a mulitple of 1)  

Tags 
modulo, number, primes 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
primes and twin primes: Number between powers of 10  caters  Number Theory  67  March 19th, 2014 04:32 PM 
Large number modulo  FloorPlay  Number Theory  2  October 30th, 2013 08:59 PM 
Modulo and Primes  emilzod  Number Theory  3  October 27th, 2013 08:33 AM 
Primes as the seeds for any number  Agno  Number Theory  53  November 19th, 2011 04:10 PM 
Number of solutions modulo p squared  fortin946  Number Theory  4  April 18th, 2011 08:21 AM 