User Name Remember Me? Password

 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.      