# High School Mathematics Extensions/Further Modular Arithmetic/Problem Set

Jump to navigation
Jump to search

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

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*^{2} ≡ *g*, then *g* is a generator mod *p*. That is *g*^{q} ≠ 1 for all *q* < *p* - 1.