Results 1 to 2 of 2

Math Help - Cryptography - Modular Arithmetic

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    1

    Cryptography - Modular Arithmetic

    This is my first post.

    I'm having a bit of trouble getting started with some questions in a text I am going though. Most of the questions are similar,so if I can get through one of them, I'm assuming it would serve as a guide to getting through the rest. Here are a few of the presented questions:


    • Let a ∈ Zn. Show that a and n are relatively prime if and only if there exists an element b ∈ Zn such that ab=1.

    I realize that to show that numbers are relatively prime, I have to show that gcd(a,n)=1 -- I guess using Euclidean Algorithm, which I know how to do with actual numbers.
    • Let a ∈ Zn. Show that a and n are relatively prime if and only if a's row in the multiplication table of Zn contains every element of Zn.

    ???
    • Show that n is a prime number if and only if in the multiplication table for Zn, except for the first row, all elements of Zn appear in each row.

    I understand what the problem is asking, but I have no idea how to begin proving it.
    If someone can shed some light or provide some guidance, it is greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    For the first question, suppose that ab \equiv 1 \mod n for some integer b but a and n are not relatively prime. Then ak \equiv 0 \mod n for some integer k such that 0 < k < n. By the first equation, abk \equiv k \mod n, but since ak \equiv 0 \mod n, abk \equiv 0 \mod n, which is a contradiction.

    Conversely, suppose that \gcd(a, n) = 1. Then there exist integers p, q such that pa + qn = 1. Hence pa = 1 - qn and pa \equiv 1 \mod n. This also means that (p + kn)a \equiv 1 \mod n, and p + kn \in \mathbb{Z}_n for some integer k.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 10th 2011, 05:21 PM
  2. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 15th 2011, 08:51 PM
  3. Modular arithmetic and cryptography
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 14th 2010, 10:19 PM
  4. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 2nd 2009, 12:17 PM
  5. Modular arithmetic
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: September 20th 2008, 09:08 AM

Search Tags


/mathhelpforum @mathhelpforum