| Blogs > exeexe |
|
exeexe
Denmark937 Posts
mod is so much easier 8 = 2 mod 6. And it becomes 2^n - 2^n mod 6 = 0 and therefore is divisible by 6 This is from another post where i saw it the first time and im like huh? So imagine you have any 2 arbitrary numbers x and y and y cant be 0 and you have the following task: Find out if x is divisable with y, how can you do that using mod?    | ||
infinitestory
United States4053 Posts
| ||
|
blankspace
United States292 Posts
Mod is just a notation but a useful one. To show 8^n congruent to 2^n mod 6 you can use the binomial theorem or subtract and factor. | ||
|
brian
United States9618 Posts
take a number X X mod Y is the remainder when x is divided by Y. 32 MOD 5 divide 32 by five the remainder is 2 32 MOD 5 =2 | ||
|
palanq
United States761 Posts
x mod y equals zero, then x* is divisible by y* edit: -_-;; | ||
|
infinitestory
United States4053 Posts
| ||
|
Axiom0
63 Posts
Also mod is technically not an operator like Gene described it as, although it is sometimes used that way. It's really an equivalence relation as blankspace described. As an answer to your other question. If x = 0 mod y, then y divides x-0 by definition (so y divides x). Using mod doesn't really give you much in that situation. | ||
Xeofreestyler
Belgium6771 Posts
maybe because it is used in arnold's cat map http://en.wikipedia.org/wiki/Arnold's_cat_map | ||
|
Emperor_Earth
United States824 Posts
If 10/3 has a remainder of 1, then 10 % 3 = 1. 10 / 3 = 3 R1 :. 10 % 3 = 1 4 / 2 = 2 R0 :. 4 % 2 = 0 6 / 200 = 0 R6 :. 6 % 200 = 6 | ||
|
infinitestory
United States4053 Posts
On August 30 2010 10:51 Axiom0 wrote: The reason why you don't understand the quoted part is because it's unjustified and skips a lot of steps. If you don't understand what he posted it's because its just sloppy mathematics and not really a fault on your part. I wouldn't go so far as to call it "unjustified." Proving a = b (mod m) implies a^n = b^n (mod m) is not difficult in any way, although it is true that 8 and 2 are not interchangeable mod 6. x^8 and x^2 are not always congruent mod 6, for example. On August 30 2010 10:51 Axiom0 wrote: Also mod is technically not an operator like Gene described it as. sidenote: modulo (%) is an operator in computer science only. | ||
|
hypercube
Hungary2735 Posts
2 mod 6 just means the remainder of 2 diveded by 6. i.e 5 mod 3 = 2 7 mod 2 = 1 etc. Find out if x is divisable with y, how can you do that using mod? x is divisible by y if x mod y = ? + Show Spoiler + x mod y = 0 The important facts about modulus that it's in some sense "compatible" with addition and multiplication. I.e if you know the values of a mod c and b mod c you also know the values of (a+b) mod c and ab mod c. You don't actually need to know the exact values of a and b just their remainder when divided by c. Specifically, you just add up (or multiply) the remainders and take their remainder again and you've got the remainder of the sum (or multiple). | ||
|
exeexe
Denmark937 Posts
x^2 mod x^(1/2) = x^2 mod sqrt(x) = ? | ||
|
Severedevil
United States4838 Posts
On August 30 2010 15:29 exeexe wrote: So what is like x^2 mod x^(1/2) = x^2 mod sqrt(x) = ? If sqrt(x) is a positive integer, the answer is 0, because x^2 = (sqrt(x))(sqrt(x))(x) which is a multiple of sqrt(x). However, mod is only an operator if you're programming. If you're doing math, you instead say that "x^2 and 0 are congruent [under] mod sqrt(x)." That way, you can also assert that 31 is congruent to 6 under mod 5, because they both have the same remainder (1) when divided by 5. The notation is "31 = 6 (mod 5)", except instead of "=", you have a similar sign with three horizontals lines that means "is congruent to" instead of "is equal to". | ||
|
love1another
United States1844 Posts
The easiest way to do such a one-to-one mapping is just to pick i in n and map it to i%m in the space of size m. | ||
|
mieda
United States85 Posts
In this case when we "mod n" for an integer n (can actually be n = 0 here) we're imposing the relation the 0 = n on the (ring of) integers and all the other relations that follow by given algebraic structures on them (in this case + and *, so all multiples of n are 0, and this is an equivalence relation). For another example where this "mod" idea is useful, just consider construction of the complex numbers. We want to enlarge the field of reals to have an element "i" such that i^2 = -1 and it's consistent with all field axioms. One way to do this is direct, but a more slick way is to just consider it as R[x]/(x^2 + 1). Here you're "modding" out the polynomial ring R[x] (R here is the field of reals) by (x^2 + 1), an ideal of R[x] generated by x^2 + 1. The image of element x in R[x]/(x^2 + 1) acts as "i," since we're imposing the condition that x^2 + 1 = 0, or x^2 = -1. Furthermore one can easily check that the natural map R -> R[x]/(x^2 + 1) is injective and is a homomorphism (in fact the kernel is an ideal so it's either 0 or R since R is a field, and clearly it's not all of R, so is 0 ideal) and you can verify that all algebraic structures are well-defined whenever you do this, and that's one value of abstracting concepts. That's one direction of generalizing "mod" for integers. You can certainly consider it as an operation, but regarding it as an equivalence relation seems to give much more interesting and deep generalizations in mathematics (building idea in abstract algebra!)  ."mod" is an idea in mathematics where you impose certain more structures to get other (hopefully more interesting!) structures. | ||
|
GrayArea
United States872 Posts
| ||
|
mieda
United States85 Posts
On August 31 2010 10:26 GrayArea wrote: What Math is this from? I have taken up to Calculus 2, and I've never seen "mod" before. You can first get introduced to "mod" stuff for integers in any intro text in *elementary* number theory (as opposed to modern number theory, which uses just about every branch of mathematics including algebraic geometry, algebraic topology (and topology ofc), combinatorics, etc..). The "mod" stuff for general algebraic structures can be found in any intro to abstract algebra texts (such as Dummit & Foote, Lang, Hungerford, etc..). For the elementary number theory part, there are many good texts that I used when I was in high school (while preparing for IMO, I made to MOSP and did well enough to be in black team but they wouldn't let me progress further because I did not have U.S. Citizenship at the time, much less a green card T_T) such as Ivan & Zuckermann (in fact this is the only intro elementary number theory book I read cover to cover and is said to be the "canonical" choice!) Here's one of the books that I read cover to cover in high school which inspired me to major in math in college: http://www.amazon.com/Introduction-Theory-Numbers-Ivan-Niven/dp/0471625469/ref=sr_1_1?ie=UTF8&s=books&qid=1283218586&sr=8-1 It also has many excellent problems, some of which were proposed for IMO longlists (back in the days) I believe. With that said, this is still elementary part of number theory. That is to say, classical 19th century stuff. Nowadays, thanks to Wiles and Taylor (who happens to be my advisor), modern number theory looks more like a fusion of algebraic geometry (with Grothendieck revolution - schemy stuff, for those of you who know what schemes / sheaf cohomology are ^^) and algebraic number theory mixed with galois representations, modular (and more generally automorphic) forms and representations. If you'd like a little taste of how number theory has developed into in the last 100 years or so, Mazur has written up a nice article titled "Number as Gadfly" Here's the link (in my dropbox): http://dl.dropbox.com/u/3799589/MazurGadfly.pdf | ||
|
EtherealDeath
United States8366 Posts
You can also interpret it as c divides (a-b) implies a = b mod c. Thus 7 = 2 mod 5 since 5 divides (7-2). Let Zc = {0, 1, 2, ..., n-1}, that is, the set of residues modulo n. In the above example where c = 5, we would have Z5 = {0,1,2,3,4}. <Zc, +, *> is a commutative ring, with addition and multiplication working as you would assume: (a mod c) + (b mod c) = (a+b) mod c (a mod c) * (b mod c) = (a*b) mod c You might wonder if there is a multiplicative inverse, that is, whether for all a in Zc, there exists a b such that (ab) mod c = (ba) mod c = 1 mod c. Yes, a has a multiplicative inverse modulo c if a and c and relatively prime. A corollary of this is that if we work in Zp where p is prime, then <Zp, +, *> is a field. That is, it has the "multiplicative identity" and "no zero divisor" properties of an integral domain as well as the "multiplicative inverse" property of a field. And to answer your question, So imagine you have any 2 arbitrary numbers x and y and y cant be 0 and you have the following task: Find out if x is divisable with y, how can you do that using mod? If x = 0 mod y, then y divides x. | ||
|
mieda
United States85 Posts
The fact that if a = b (mod n) then a^k = b^k (mod n) is just repeated applications of the above (and in particular 8^n = 2^n (mod 6), which solves the problem that started this all ^^). Once basic facts are proved (that the operations are well-defined, fermat's little theorem (and more generally lagrange's theorem applied to the multiplicative structure on Zc), gcd stuff, etc.. the "elementary" number theory things) you're in a position to handle questions that are otherwise more difficult to handle without the language and the basic facts of the theory. I can list a few well-known (hopefully interesting) exercises here where you can try doing them without resorting to aforementioned facts and perhaps you can appreciate how easy they would be once the basic facts of elementary number theory are down: 1) for p odd prime, and 1/1 + 1/2 + ... + 1/(p-1) = a/b for integers with gcd(a,b) = 1, p divides b (in fact p^2 divides b but this requires a slight more work). 2) for any integer m > 0, the sequence 2, 2^2, 2^(2^2), 2^(2^(2^2)), ... defined by a_1 = 2 and a_n = 2^(a_(n-1)) eventually leaves same remainder upon division by m. I think this is actually an old USAMO problem. 3) (p-1)! + 1 is divisible by p for any odd prime p ^^. This is near trivial once you understand the structure of Z/p (integers mod p) as being a field. 4) many more! ^^ | ||
|
blankspace
United States292 Posts
Pair up the sum into pairs 1/x + 1/(p-x) = p/[x(p-x)]. If we group up stuff we get p(x/y) = a/b or pxb = ay. p cannot divide y because the lcm of (1,2...p-1) does not contain p so p divides a. | ||
|
mieda
United States85 Posts
On August 31 2010 13:25 blankspace wrote: 1. don't you mean p divides a? 1 + 1/2 + 1/3 + 1/4 = 25/12 for example. Pair up the sum into pairs 1/x + 1/(p-x) = p/[x(p-x)]. If we group up stuff we get p(x/y) = a/b or pxb = ay. p cannot divide y because the lcm of (1,2...p-1) does not contain p so p divides a. Yes, i mean p divides a. Thanks for the correction. Likewise, (in fact) p^2 divides a, but this requires one more easy pairing, which I leave up to the reader ^^ | ||
|
crazeman
664 Posts
On August 31 2010 10:26 GrayArea wrote: What Math is this from? I have taken up to Calculus 2, and I've never seen "mod" before. Mod also shows up in programming classes. Chances are, if you took one before, you've probably seen it. | ||
|
Hidden_MotiveS
Canada2562 Posts
| ||
|
GrayArea
United States872 Posts
On August 31 2010 10:33 mieda wrote: You can first get introduced to "mod" stuff for integers in any intro text in *elementary* number theory (as opposed to modern number theory, which uses just about every branch of mathematics including algebraic geometry, algebraic topology (and topology ofc), combinatorics, etc..). The "mod" stuff for general algebraic structures can be found in any intro to abstract algebra texts (such as Dummit & Foote, Lang, Hungerford, etc..). For the elementary number theory part, there are many good texts that I used when I was in high school (while preparing for IMO, I made to MOSP and did well enough to be in black team but they wouldn't let me progress further because I did not have U.S. Citizenship at the time, much less a green card T_T) such as Ivan & Zuckermann (in fact this is the only intro elementary number theory book I read cover to cover and is said to be the "canonical" choice!) Here's one of the books that I read cover to cover in high school which inspired me to major in math in college: http://www.amazon.com/Introduction-Theory-Numbers-Ivan-Niven/dp/0471625469/ref=sr_1_1?ie=UTF8&s=books&qid=1283218586&sr=8-1 It also has many excellent problems, some of which were proposed for IMO longlists (back in the days) I believe. With that said, this is still elementary part of number theory. That is to say, classical 19th century stuff. Nowadays, thanks to Wiles and Taylor (who happens to be my advisor), modern number theory looks more like a fusion of algebraic geometry (with Grothendieck revolution - schemy stuff, for those of you who know what schemes / sheaf cohomology are ^^) and algebraic number theory mixed with galois representations, modular (and more generally automorphic) forms and representations. If you'd like a little taste of how number theory has developed into in the last 100 years or so, Mazur has written up a nice article titled "Number as Gadfly" Here's the link (in my dropbox): http://dl.dropbox.com/u/3799589/MazurGadfly.pdf Thank you for this very detailed post! I haven't done any number theory classes which explain my ignorance on mods. Also, thanks for posting the article. I skimmed through it, but it's way too heavy for me and over my head so I passed it up haha. Anyway, good luck with your studies! | ||
|
exeexe
Denmark937 Posts
| ||
| ||
|
|
Wardi Open
Sparkling Tuna Cup
WardiTV European League
Online Event
uThermal 2v2 Circuit
The PondCast
Replay Cast
Korean StarCraft League
CranKy Ducklings
Sparkling Tuna Cup
|
|
|
EPT
