Day 06Part 07- Discrete mathematics for computer engineering- Trick for finding of group of finite numbers.<\/p>\n
[fvplayer id=”168″]<\/p>\n
In Discrete Mathematics<\/strong>, a group<\/strong> is a set of finite numbers with a binary operation that satisfies the following properties: Check Closure<\/strong> \u2192 Perform the operation on all elements and ensure the result is still in the set. Consider the set Z\u2086 = {0, 1, 2, 3, 4, 5}<\/strong> under addition modulo 6<\/strong>.<\/p>\n Closure:<\/strong> Adding any two numbers from Z\u2086 modulo 6 gives another element in Z\u2086. 1 \u2192 5 (because 1+5\u22610mod\u2009\u200961+5 \\equiv 0 \\mod 6<\/span>1<\/span>+<\/span><\/span>5<\/span>\u2261<\/span><\/span>0<\/span><\/span>mod<\/span><\/span>6<\/span><\/span><\/span><\/span>)<\/p>\n<\/li>\n 2 \u2192 4 (because 2+4\u22610mod\u2009\u200962+4 \\equiv 0 \\mod 6<\/span>2<\/span>+<\/span><\/span>4<\/span>\u2261<\/span><\/span>0<\/span><\/span>mod<\/span><\/span>6<\/span><\/span><\/span><\/span>)<\/p>\n<\/li>\n 3 \u2192 3 (self-inverse)<\/p>\n<\/li>\n<\/ul>\n Conclusion:<\/strong> (Z\u2086, +) is a Group.<\/strong><\/p>\n Consider Z\u2086 = {0, 1, 2, 3, 4, 5}<\/strong> under multiplication modulo 6<\/strong>.<\/p>\n Closure:<\/strong> Some results are not in Z\u2086 (e.g., 2\u00d73=6\u22610mod\u2009\u200962 \u00d7 3 = 6 \\equiv 0 \\mod 6<\/span>2<\/span>\u00d7<\/span><\/span>3<\/span>=<\/span><\/span>6<\/span>\u2261<\/span><\/span>0<\/span><\/span>mod<\/span><\/span>6<\/span><\/span><\/span><\/span>, but 6 is not in Z\u2086). Conclusion:<\/strong> (Z\u2086, \u00d7) is NOT a Group.<\/strong><\/p>\n \u00a0If the operation is addition modulo n<\/strong>, it usually forms a group. Would you like more examples or specific tricks<\/strong> for other types of groups?<\/p>\n
Closure<\/strong> \u2013 If a,ba, b<\/span>a<\/span>,<\/span>b<\/span><\/span><\/span><\/span> are in the set, then a\u2217ba * b<\/span>a<\/span>\u2217<\/span><\/span>b<\/span><\/span><\/span><\/span> is also in the set.
Associativity<\/strong> \u2013 (a\u2217b)\u2217c=a\u2217(b\u2217c)(a * b) * c = a * (b * c)<\/span>(<\/span>a<\/span>\u2217<\/span><\/span>b<\/span>)<\/span>\u2217<\/span><\/span>c<\/span>=<\/span><\/span>a<\/span>\u2217<\/span><\/span>(<\/span>b<\/span>\u2217<\/span><\/span>c<\/span>)<\/span><\/span><\/span><\/span> for all elements in the set.
Identity Element<\/strong> \u2013 There exists an element ee<\/span>e<\/span><\/span><\/span><\/span> such that a\u2217e=e\u2217a=aa * e = e * a = a<\/span>a<\/span>\u2217<\/span><\/span>e<\/span>=<\/span><\/span>e<\/span>\u2217<\/span><\/span>a<\/span>=<\/span><\/span>a<\/span><\/span><\/span><\/span>.
Inverse Element<\/strong> \u2013 For each aa<\/span>a<\/span><\/span><\/span><\/span>, there is an element a\u22121a^{-1}<\/span>a<\/span>\u22121<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> such that a\u2217a\u22121=ea * a^{-1} = e<\/span>a<\/span>\u2217<\/span><\/span>a<\/span>\u22121<\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>e<\/span><\/span><\/span><\/span>.<\/p>\n\u00a0Quick Trick to Check if a Finite Set Forms a Group<\/strong><\/h3>\n
Check Associativity<\/strong> \u2192 Pick any three elements and verify the associative property.
Find the Identity Element<\/strong> \u2192 Find an element ee<\/span>e<\/span><\/span><\/span><\/span> such that a\u2217e=aa * e = a<\/span>a<\/span>\u2217<\/span><\/span>e<\/span>=<\/span><\/span>a<\/span><\/span><\/span><\/span> for all aa<\/span>a<\/span><\/span><\/span><\/span>.
Find Inverses<\/strong> \u2192 Each element should have an inverse under the given operation.<\/p>\n\u00a0Example 1: Checking if (Z\u2086, +) is a Group<\/strong><\/h3>\n
Associativity:<\/strong> Modulo addition is associative.
Identity Element:<\/strong> 0 is the identity because a+0=aa + 0 = a<\/span>a<\/span>+<\/span><\/span>0<\/span>=<\/span><\/span>a<\/span><\/span><\/span><\/span>.
Inverses Exist:<\/strong> Each element has an inverse:<\/p>\n\n
\u00a0Example 2: Checking if (Z\u2086, \u00d7) is a Group<\/strong><\/h3>\n
Identity:<\/strong> There is no element ee<\/span>e<\/span><\/span><\/span><\/span> such that a\u00d7e=aa \u00d7 e = a<\/span>a<\/span>\u00d7<\/span><\/span>e<\/span>=<\/span><\/span>a<\/span><\/span><\/span><\/span> for all aa<\/span>a<\/span><\/span><\/span><\/span>.
Inverses:<\/strong> Some elements have no inverses.<\/p>\n\u00a0Shortcut Rule for Small Sets<\/strong><\/h3>\n
\u00a0If the operation is multiplication modulo n<\/strong>, check for the existence of an identity element and inverses<\/strong>.
\u00a0The set of nonzero elements modulo a prime number (Z\u209a{0}, \u00d7 mod p)<\/strong> always forms a group<\/strong>.<\/p>\n