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
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
niravshah99 is offline  
 
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.
brangelito is offline  
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
niravshah99 is offline  
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.
cknapp is offline  
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)
brangelito is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.