High School Mathematics Extensions/Further Modular Arithmetic/Problem Set

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

HSME
Content
Further Modular Arithmetic
Multiplicative Group and Discrete Log
Problems & Projects
Problem Set
Project
Solutions
Exercises Solutions
Problem Set Solutions
Misc.
Definition Sheet
Full Version
PDF Version

1. Suppose in mod m arithmetic we know x ≠ y and

$y^{2}\equiv x^{2}{\pmod {m}}\!$

find at least 2 divisors of m.

2. Derive the formula for the Carmichael function, λ(m) = smallest number such that a^λ(m) ≡ 1 (mod m).

3. Let p be prime such that p = 2^s + 1 for some positive integer s. Show that if g is not a square in mod p, i.e. there's no h such that h² ≡ g, then g is a generator mod p. That is g^q ≠ 1 for all q < p - 1.