My Math Forum Why primes number when doing modulo?

 Number Theory Number Theory Math Forum

 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...m-1} 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:
 Originally Posted by niravshah99 How does that help ? So what if it is co prime to every other number
Let's look at a simple example:
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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post caters Number Theory 67 March 19th, 2014 04:32 PM FloorPlay Number Theory 2 October 30th, 2013 08:59 PM emilzod Number Theory 3 October 27th, 2013 08:33 AM Agno Number Theory 53 November 19th, 2011 04:10 PM fortin946 Number Theory 4 April 18th, 2011 08:21 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top