# Exercise 1 Cheat Sheet
## Multiplicative Groups of (Z/nZ)*

---

## Recognition

Use this algorithm when asked to:

- Find the order of an element.
- Count elements of order k.
- Find all elements of order k.

If

    n = p * q

then

    ┌─────────────────────────────────────────────────┐
    │  (Z/nZ)*  ≅  (Z/pZ)*  ×  (Z/qZ)*               │
    └─────────────────────────────────────────────────┘

Always split with the Chinese Remainder Theorem (CRT).

---

## Facts

    |(Z/pZ)*| = p-1,    |(Z/nZ)*| = (p-1)(q-1)

Each (Z/pZ)* is cyclic.

    ┌──────────────────────────────────────────────────────┐
    │  ord(x) = lcm( ord(x_p), ord(x_q) )                 │
    └──────────────────────────────────────────────────────┘

A cyclic group has exactly

    ┌────────────────────────────────┐
    │  φ(d)  elements of order d     │
    └────────────────────────────────┘

---

## (a) Find the Order of a

**1. Factor n.**

    n = p * q

GAP:
```
FactorsInt(n);
```

**2. Compute orders modulo each prime.**

Since

    a^(p-1) ≡ 1 (mod p)

the order divides p-1.

Start with

    t = p-1

Factor t.

For every prime divisor r:

    ┌───────────────────────────────────────────────────────┐
    │  while  a^(t/r) ≡ 1 (mod p),   t ← t / r            │
    └───────────────────────────────────────────────────────┘

Idea: repeatedly shrink the exponent until it cannot be reduced.

Then

    t = t_p = ord(a mod p)

Repeat for q to obtain t_q.

Useful GAP:
```
FactorsInt(p-1);
PowerMod(a, e, p);
OrderMod(a, p);            (verification)
```

**3. Combine**

    ┌─────────────────────────────────────────────┐
    │  ord(a) = lcm(t_p, t_q)                     │
    └─────────────────────────────────────────────┘

GAP:
```
Lcm(tp, tq);
```

---

## (b) Count Elements of Order k

**1. List divisors**

    d1 | (p-1),    d2 | (q-1)

GAP:
```
DivisorsInt(p-1);
DivisorsInt(q-1);
```

**2. Keep only**

    ┌──────────────────────────────────────────────┐
    │  lcm(d1, d2) = k                             │
    └──────────────────────────────────────────────┘

**3. Count**

A cyclic group contributes

    φ(d)  elements of order d

Therefore

    ┌────────────────────────────────────────────────┐
    │   Σ           φ(d1) * φ(d2)                    │
    │  lcm(d1,d2)=k                                  │
    └────────────────────────────────────────────────┘

GAP:
```
Phi(d);
```

---

## (c) Find All Elements of Order k

**1. Find valid sub-orders**

List

    d1 | (p-1),    d2 | (q-1)

and keep only

    ┌──────────────────────────────────────────────┐
    │  lcm(d1, d2) = k                             │
    └──────────────────────────────────────────────┘

**2. Find generators**

Test small integers (2, 3, 5, ...) until one passes:

    g^((p-1)/r) ≢ 1 (mod p)

for every prime divisor r of p-1.

Repeat for q.

GAP:
```
GeneratorsPrimeResidues(p);
```

**3. Build all subgroup elements**

For each valid pair (d1, d2):

    a = g_p^((p-1)/d1),    b = g_q^((q-1)/d2)

These produce one element of orders d1 and d2.

To obtain *all* elements:

    a^m,   1 ≤ m < d1,   gcd(m, d1) = 1
    b^n,   1 ≤ n < d2,   gcd(n, d2) = 1

There are exactly

    φ(d1),   φ(d2)

such elements.

Manual shortcut:

- List 1, ..., d-1.
- Cross out multiples of every prime factor of d.
- Remaining exponents are exactly the coprime ones.

**4. Combine with CRT**

For every pair (a^m, b^n) solve

    x ≡ a^m (mod p),    x ≡ b^n (mod q)

Each CRT solution has order k.

GAP:
```
ChineseRem(a, p, b, q);
```

---

## Workflow

    ┌────────────────────────────────────────────────────────────┐
    │  Factor n                                                 │
    │      ↓                                                    │
    │  CRT                                                      │
    │      ↓                                                    │
    │  ┌──────────────────────────────────────────────────────┐ │
    │  │ (a) Find t_p, t_q → LCM                              │ │
    │  │ (b) Divisors → φ(d1)*φ(d2)                           │ │
    │  │ (c) Generators → g^((p-1)/d) → CRT                   │ │
    │  └──────────────────────────────────────────────────────┘ │
    └────────────────────────────────────────────────────────────┘

---

## Common Mistakes

- Never compute the order directly modulo n; split with CRT first.
- Orders combine by **LCM**, never multiplication.
- φ(d) counts elements of order d only because each (Z/pZ)* is cyclic.
- To obtain *all* elements of order d, use every exponent coprime to d.
- Before counting or constructing elements of order k, verify there exist
  d1 | (p-1), d2 | (q-1) such that lcm(d1, d2) = k.