mersenneforum.org > Math Congruence
 Register FAQ Search Today's Posts Mark Forums Read

2009-09-13, 18:30   #1
storm5510
Random Account

Aug 2009
U.S.A.

25×53 Posts
Congruence

Quote:
 In mathematics and especially in abstract algebra as well as modular arithmetic, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s).
Someone, explain this in simple terms. Please, no links to other sites...

 2009-09-13, 18:57 #2 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 17×251 Posts Here's my understanding of it, simple as can be: (for modular arithmetic, at least) 13 is congruent to 1 modulo 12 because each are one higher than a multiple of 12. Or in formula form: $13 \equiv 1 \hspace{1} (\text{mod } 12)$ Where $\equiv$ means congruent to.
 2009-09-13, 21:28 #3 Dougy     Aug 2004 Melbourne, Australia 2308 Posts Congruence'' means equivalence'' in some sense. This is one of the words in mathematics that has many meanings depending on what area of mathematics your interested in (eg. there are congruent triangles also). Typically in number theory... two integers are congruent modulo m if they have the same remainder after division by m. In Mini-Geek's example m=12. We see that 13 after division by 12 leaves a remainder 1. Similarly, 1 after division by 12 also leaves a remainder 1. In fact, all of the numbers in $\{1,13,25,\dots\}$ are congruent modulo 12. This can also be extended to negative integers too, so $\{\dots,-23,-11,1,13,25,\dots\}$ are all congruent modulo 12.
2009-09-13, 21:56   #4
lfm

Jul 2006
Calgary

42510 Posts

Quote:
 Originally Posted by storm5510 Someone, explain this in simple terms. Please, no links to other sites...
I usually read it as "referring to the same thing". Like 13:00 in a 24 hour time vs 1:00 PM in a 12 hour time system (13 = 1 (mod 12)) they are referring to the same time of day. So the various base 10 numbers when mapped into a (mod x) system are just different representations for the same end value referring to the same end result with different symbols. It no different from converting base 10 to binary or hexadecimal. It is the same number with different symbols 10(base 10) is congruent 1010(base 2).

IANAM so YMMV

2009-09-13, 23:16   #5
storm5510
Random Account

Aug 2009
U.S.A.

25×53 Posts

The reason I ask is I was trying to understand what is below:

Quote:
 The Algorithm of Miller-Rabin primality test for an odd integer n 1. We write n-1 = 2^k*m where k is integer and m is an odd number. 2. We choose a random integer "a" where it is between 1 to n-1. 3. Then calculate b = a^m mod n. 4. If b is congruent to 1 modulo n, then print "n is prime" and quit. 5. For i = 0 to k - 1 do 6. if b is congruent to (-1) modulo n,then print "n is prime" and quit; else b = b^2 mod n. 7. Otherwise, print "n is composite".
92 and 81 are congruent, for example.

Last fiddled with by storm5510 on 2009-09-14 at 00:05

2009-09-14, 00:48   #6
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts

In other words:
Quote:
 3. Then calculate b = a^m mod n.
define b to be the remainder of a^m divided by n
Quote:
 4. If b is congruent to 1 modulo n, then print "n is prime" and quit.
if b divided by n has a remainder of 1, then print "n is prime" and quit.
Quote:
 6. if b is congruent to (-1) modulo n,then print "n is prime" and quit; else b = b^2 mod n.
if b divided by n has a remainder that is one less than n (e.g. 19/10 has a remainder of 9, which is 10-1), then print "n is prime" and quit; else define b to be the remainder when b^2 is divided by n.

(I'll assume you understand the rest of it, like the 'for' loop)

http://en.wikipedia.org/wiki/Miller%...primality_test has explanations, pseudocode, an example, etc.

Last fiddled with by Mini-Geek on 2009-09-14 at 00:52

 2009-09-14, 01:34 #7 storm5510 Random Account     Aug 2009 U.S.A. 25·53 Posts I wasn't much concerned with the rest. Just the term. I rather doubt something like this could be coded, reliably anyway. Thanks.
2009-09-14, 02:49   #8
bsquared

"Ben"
Feb 2007

23×419 Posts

Quote:
 Originally Posted by storm5510 I rather doubt something like this could be coded, reliably anyway. Thanks.
What do you mean? Many people on this forum have implemented it, myself included. Where are you getting stuck?

2009-09-14, 02:51   #9
lfm

Jul 2006
Calgary

1A916 Posts

Quote:
 Originally Posted by storm5510 I wasn't much concerned with the rest. Just the term. I rather doubt something like this could be coded, reliably anyway. Thanks.
huh? Miller-Rabin tests are coded all the time. It is often what is behind "probable prime tests".

2009-09-14, 16:02   #10
storm5510
Random Account

Aug 2009
U.S.A.

25·53 Posts

Quote:
 Originally Posted by lfm huh? Miller-Rabin tests are coded all the time. It is often what is behind "probable prime tests".
I should have said, I couldn't code it reliably. I saw examples in other platforms, and pseudocode below from Wikipedia.

Quote:
 Input: n > 2, an odd integer to be tested for primality; Input: k, a parameter that determines the accuracy of the test Output: composite if n is composite, otherwise probably prime write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1 LOOP: repeat k times: pick a randomly in the range [2, n − 1] x ← ad mod n if x = 1 or x = n − 1 then do next LOOP for r = 1 .. s − 1 x ← x2 mod n if x = 1 then return composite if x = n − 1 then do next LOOP return composite return probably prime

2009-09-14, 18:33   #11
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by storm5510 I should have said, I couldn't code it reliably. I saw examples in other platforms, and pseudocode below from Wikipedia.
If you will explain where you are getting stuck, perhaps help
might be offered.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Software 14 2017-07-13 19:54 Lee Yiyuan Miscellaneous Math 7 2012-05-08 12:55 meknowsnothing Math 1 2007-05-31 03:32 abiessuunreg Miscellaneous Math 3 2005-03-07 21:03

All times are UTC. The time now is 03:06.

Fri Dec 4 03:06:26 UTC 2020 up 23:17, 0 users, load averages: 1.62, 1.88, 1.84