
	Trending ▼ ICSE CBSE 10th ISC CBSE 12th CTET GATE UGC NET Vestibulares ResFinder

3rd Year Textbook 2017 : Mathematics (University of Allahabad (UoA), Allahabad)

12 pages, 0 questions, 0 questions with responses, 0 total responses,

ARUN verma
University of Allahabad (UoA), Allahabad

+Fave Message

Profile Timeline Uploads

Home > 123490 > F Also featured on: School Page

Formatting page ...

CYCLICITY OF (Z/(p)) KEITH CONRAD 1. Introduction For any prime p, the group (Z/(p)) is cyclic. We will give six proofs of this fundamental result. A common feature of the proofs that (Z/(p)) is cyclic is that they are non-constructive. Up to this day, there is no algorithm known for finding a generator of (Z/(p)) other than a brute force search: try a = 2, 3, . . . until you find an element with order p 1. While the proof that a generator of (Z/(p)) exists is non-constructive, in practice it does not take long to find a generator by a brute-force search. The non-constructive proof that a generator exists gives us the confidence that our search for a generator will be successful before we even begin. By comparison, for most (but not all) non-prime m the group (Z/(m)) is not cyclic. For example, (Z/(12)) is not cyclic: it has size 4 but each element has order 1 or 2. While the cyclicity of (Z/(p)) is important in algebra, it also has practical significance. A choice of generator of (Z/(p)) is one of the ingredients in two public key cryptosystems: Diffie-Hellman (this is the original public key system, if we discount earlier classified work by British intelligence) and ElGamal. You can find out how these cryptosystems work by doing a web search on their names. The following result is needed in all but one proof that (Z/(p)) is cyclic, so we state it first. Theorem 1.1. For any r 1, there are at most r solutions to the equation ar = 1 in Z/(p). A proof of Theorem 1.1 is given in Appendix A. Theorem 1.1 is a special case of a broader result on polynomials: any polynomial with coefficients in Z/(p) has no more roots in Z/(p) than its degree. (The link to Theorem 1.1 is that the equation ar = 1 is satisfied by the roots of the polynomial T r 1, whose degree is r.) This upper bound breaks down in Z/(m) for non-prime m, e.g., the polynomial T 2 1 has four solutions in Z/(8). 2. First Proof: A -identity For our first proof that (Z/(p)) is cyclic, we are going to count the elements with various orders. In (Z/(p)) , which has size p 1, the order of any element divides p 1. For each positive divisor of p 1, say d, let Np (d) be the number of elements of order d in (Z/(p)) . For instance, Np (1) = 1 and the cyclicity of (Z/(p)) , which we want to prove, is equivalent to Np (p 1) > 0. Every element has some order, so counting the elements of the group by order yields Np (d) = p 1. (2.1) d|(p 1) 1

Formatting page ...

123490 chat

Horizontal lines at:
Guest Horizontal lines at:
AutoRM Data:
Box geometries: