Groups

The axioms, examples (integers mod n, symmetries, permutations), order of an element.

A group is a set with an associative operation, an identity and inverses. The integers mod 7 under addition; the non-zero ones under multiplication; the six symmetries of a triangle. Picture it: the rotations and reflections of a triangle composing — that is the group S₃ acting. Think it: "3¹⁰⁰ mod 7" is a computation in the cyclic group (ℤ/7)*, whose order 6 is why Fermat's little theorem works.

ਕੰਮ ਉਦਾਹਰਨ: `3^100 mod 7`

Number-Theory · Modular-Arithmetic

3^100 mod 7

3,\ 100,\ 7

ਕਦਮ ਦਰ ਕਦਮ

3^{100} \bmod 7
Never compute the huge power. Reduce after every multiplication (repeated squaring).
3 \equiv 3 \pmod{7}
Reduce the base first.
100 = 1100100_2
Write the exponent in binary: 7 squarings at most.
3^2 \equiv 2 \pmod{7}
Square the running power.
2^2 \equiv 4 \pmod{7}
Square the running power.
r \leftarrow r \cdot 4 \equiv 4 \pmod{7}
This bit is 1: multiply the result by the current power.
4^2 \equiv 2 \pmod{7}
Square the running power.
2^2 \equiv 4 \pmod{7}
Square the running power.
4^2 \equiv 2 \pmod{7}
Square the running power.
r \leftarrow r \cdot 2 \equiv 1 \pmod{7}
This bit is 1: multiply the result by the current power.
2^2 \equiv 4 \pmod{7}
Square the running power.
r \leftarrow r \cdot 4 \equiv 4 \pmod{7}
This bit is 1: multiply the result by the current power.
3^{100} \equiv 4 \pmod{7}
Done.

ਜਵਾਬ ਦਿਓ

3^{100} \bmod 7 = 4

Symbols used here

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

\pm

plus or minus
Both signs at once: x = 3 ± 2 means 5 and 1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

a \bmod n

remainder
What is left after dividing a by n.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

\operatorname{Hom}(A, B),\ f \circ g

arrows from A to B, composition
The set of morphisms; do g then f.

How to: Groups

Check closure: the operation of any two elements stays in the set.
Find the identity element.
Find each element's inverse.
Associativity usually comes for free from the underlying arithmetic; say why.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

ਆਪਣਾ ਹੀ ਕੋਸ਼ਿਸ਼ ਕਰੋ

ਹੋਰ ਵਿੱਚ Abstract Algebra

Subgroups, cosets and Lagrange's theorem Cyclic groups and permutation groups Homomorphisms, normal subgroups and quotient groups Rings and fields Galois theory: why the quintic has no formula

ਕੰਮ ਉਦਾਹਰਨ: 3^100 mod 7