High School Mathematics Extensions/Further Modular Arithmetic/Problem Set

From Wikibooks, open books for an open world
< High School Mathematics Extensions‎ | Further Modular Arithmetic
Jump to: navigation, search
HSME
Content
100%.svg Further Modular Arithmetic
100%.svg Multiplicative Group and Discrete Log
Problems & Projects
100%.svg Problem Set
100%.svg Project
Solutions
100%.svg Exercises Solutions
50%.svg Problem Set Solutions
Misc.
Definition Sheet
Full Version
PDF Version

1. Suppose in mod m arithmetic we know xy 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 = 2s + 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 h2g, then g is a generator mod p. That is gq ≠ 1 for all q < p - 1.