{"id":54,"date":"2018-07-21T09:54:17","date_gmt":"2018-07-21T09:54:17","guid":{"rendered":"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=54"},"modified":"2018-12-27T09:56:10","modified_gmt":"2018-12-27T09:56:10","slug":"number-theory","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/chapter\/number-theory\/","title":{"rendered":"Number Theory"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n\u00d8\u00a0 To understand the basic exponential and logarithmic functions\r\n\r\n\u00d8\u00a0\u00a0 To understand the basic outline to\r\n\r\n \r\n

o\u00a0\u00a0 prime numbers<\/p>\r\n

o\u00a0\u00a0 Primality Testing<\/p>\r\n

o\u00a0\u00a0 Primitive Roots & Discrete Logarithms<\/p>\r\n

o\u00a0\u00a0 Euclidean and Extended Euclidean Algorithms.<\/p>\r\n \r\n\r\n \r\n\r\n5.1 Introduction<\/strong>\r\n\r\n \r\n

Number theory is a branch of pure mathematics <\/a>devoted primarily to the study of integers. <\/a>It is sometimes called \"The Queen of Mathematics\" because of its foundational place in the discipline. The encryption algorithms depends heavily on modular arithmetic. We need to develop various machinery (notations and techniques) for manipulating numbers before can describe algorithms in a natural fashion.First we start with divisors.<\/p>\r\n\r\n<\/div>\r\n \r\n

\r\n\r\n5.2 Set of Integers<\/strong>\r\n\r\n \r\n

The set of integers, denoted by Z, contains all integral numbers (with no fraction) from negative infinity to positive infinity. The integers are made up of positive numbers, negative numbers and zero. The positive numbers are like the naturals, but with a \"plus\" before:+1, +2, +3 \u2026.. Nevertheless, the \"plus\" of the positive numbers does not need to be be written. On the other hand, the negative numbers are like the naturals but with a \"minus\" before:-1,-2,-3\u2026. The number zero is special, because it is the only one that has neither a plus nor a minus, showing that it is neither positive nor negative. For example, the following numbers are integers:<\/p>\r\n \r\n\r\n \r\n

Z = {\u2026..,-3,-2,-1,0,1,2,3,\u2026..}<\/p>\r\n \r\n\r\n \r\n\r\n \r\n\r\n5.3 Binary Operations<\/strong>\r\n\r\n \r\n

In cryptography, we are interested in three binary operations applied to the set of integers. A binary operation takes two inputs and creates one output. A binary operation on A is a rule that assigns to every pair of elements of A a unique element of A.<\/p>\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n<\/div>\r\n \r\n

\r\n\r\n5.4 Integer Division<\/strong>\r\n\r\n \r\n

\u00d8\u00a0 In integer arithmetic, if we divide a by n, we can get q and r . The relationship between these four integers can be shown as<\/p>\r\n \r\n

a = q \u00d7 n + r<\/strong><\/p>\r\n \r\n\r\n\u00d8\u00a0 Assume that a = 255 and n = 11. We can find q = 23 and R = 2 using the division algorithm.\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n5.4.1 Integer Division Properties<\/strong>\r\n\r\n \r\n\r\n\u00d8\u00a0 Property 1: if a\\1, then a=+\/- 1.\r\n\r\n\u00d8\u00a0\u00a0 Property 2: if a\\b and b\\a, then a=+\/-b.\r\n\r\n\u00d8\u00a0\u00a0 Property 3: if a\\b and b\\c, then a\\c.\r\n\r\n\u00d8\u00a0\u00a0 Property 4: if a\\b and a\\c, then a\\(m*b+n*c), where m and n are arbitrary integers.\r\n\r\n<\/div>\r\n \r\n

\r\n\r\n\u00a0 \u00a0 5.5 Divisors<\/strong>\r\n\r\n \r\n\r\n5.5.1<\/strong>\u00a0\u00a0\u00a0\u00a0 Definition<\/strong>\r\n\r\n \r\n\r\nLet a, b and c be integers such that\r\n

a = b \u00b7c<\/p>\r\n \r\n

Then b and c are said to divide (or are factors) of a, while a is said to be a multiple of b (as well as of c). The pipe symbol \u201c|\u201d denotes \u201cdivides\u201d so the situation is summarized by:<\/p>\r\n \r\n

b | a\u00a0\u00a0\u00a0\u00a0^ \u00a0 c | a<\/p>\r\n \r\n\r\n5.5.2<\/strong>\u00a0\u00a0\u00a0\u00a0 Examples<\/strong>\r\n\r\n \r\n\r\nWhich of the following is true?\r\n\r\n \r\n\r\n1.\u00a0 77 | 7\r\n\r\n2.\u00a0 7 | 77\r\n\r\n3.\u00a0 24 | 24\r\n\r\n4.\u00a0 0 | 24\r\n\r\n5.\u00a0 24 | 0\r\n\r\n \r\n\r\nAnswer:\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 77 | 7: false bigger number can\u2019t divide smaller positive number\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 7 | 77: true because 77 = 7 \u00b7<\/em> 11\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 24 | 24: true because 24 = 24 \u00b7<\/em> 1\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 0 | 24: false, only 0 is divisible by 0\r\n\r\n5.\u00a0\u00a0\u00a0\u00a0\u00a0 24 | 0: true, 0 is divisible by every number (0 = 24 \u00b7<\/em> 0)\r\n\r\n \r\n\r\n5.5.3 Facts<\/strong>\r\n\r\n \r\n\r\nFact 1: The integer 1 has only one divisor, itself.\r\n\r\nFact 2: Any positive integer has at least two divisors.1 and itself(but it can have more)\r\n\r\n<\/div>\r\n \r\n

\r\n\r\n5.6 GCD<\/strong>\r\n\r\n \r\n

The greatest common divisor of two positive integers is the largest integer that can divide both integers.\u00a0\u00a0\u00a0\u00a0 When gcd (a, b) = 1, we say that a and b are relatively prime.<\/p>\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n5.6.1 Relatively Prime Numbers & GCD<\/strong>\r\n\r\n \r\n\r\n\u2022\u00a0 Two numbers a,b are relatively prime (co prime) if they have no common divisors apart from 1\r\n\r\n \r\n

eg. 8 and 15 are relatively prime since factors of 8 are 1,2,4,8 and of 15 are 1, 3, 5,15 and 1 is the only common factor<\/p>\r\n \r\n

\u2022\u00a0\u00a0 Conversely can determine the greatest common divisor by comparing their prime factorizations and using least powers<\/p>\r\n \r\n

eg. 300 = 2^1x3^1x5^2 ; 18<\/p>\r\n

=\u00a0\u00a0 2^1x3^2 hence GCD(18,300)<\/p>\r\n

=\u00a0\u00a0 2^1x3^1x5^0 = 6<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n5.6.2 GCD Example<\/strong>\r\n\r\n \r\n\r\nFind the greatest common divisor of 140 and 12.\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n5.6.3 GCD using Extended Euclidean Algorithm<\/strong>\r\n\r\n \r\n\r\nGiven two integers a and b, we often need to find other two integers, s and t, such that\r\n\r\n\"\"\r\n\r\n<\/div>\r\n
\r\n\r\nExample<\/strong>\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n5.7 PRIME NUMBERS<\/strong>\r\n\r\n \r\n

Prime numbers only have divisors of 1 and self \u2013 they cannot be written as a product of other numbers \u2013 note: 1 is Prime, but is generally not of interest<\/p>\r\n \r\n\r\n\u2022\u00a0 Eg. 2,3,5,7 are prime, 4, 6, 8,9,10 are not\r\n\r\n\u2022\u00a0\u00a0 Prime numbers are central to number theory\r\n\r\n\u2022\u00a0 List of prime number less than 200 is: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53\r\n\r\n59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163\r\n\r\n167 173 179 181 191 193 197 199\r\n\r\n \r\n\r\n5.7.1 PRIME FACTORIZATION<\/strong>\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0 Let us factorize the any number n: n = a x b x c\r\n

\u2022\u00a0\u00a0 Factoring a number is relatively hard compared to multiplying the factors together to generate the number<\/p>\r\n

\u2022\u00a0 The prime factorisation of a number n is when its written as a product of primes \u2013 eg. 91 = 7 x 13; 3600 = 2^4 x 3^2 x 5^2<\/p>\r\n \r\n\r\n \r\n\r\n \r\n\r\n5.7.2 PRIMITIVE ROOTS<\/strong>\r\n\r\n \r\n\r\n \r\n\r\nIf n<\/em> is a positive integer, the integers between 1 and n<\/em> \u2212 1 that are coprime <\/a>to n<\/em> (or equivalently, the congruence classes <\/a>coprime to n<\/em>) form a group <\/a>with multiplication modulo <\/a>n<\/em> as the operation; it is denoted by Zn<\/em>\u00d7 <\/a>and is called the group\u00a0<\/a>of units <\/a>modulo <\/span>n<\/em> or the group of primitive classes modulo <\/span>n<\/em>. As explained in the article <\/span>multiplicative group of integers modulo n<\/em>, <\/a>this group is <\/span>cyclic <\/a>if and only if <\/span>n<\/em> is equal to 2, 4, <\/span>p<\/em>k<\/em>, or 2<\/span>p<\/em>k<\/em> where <\/span>p<\/em>k<\/em> is a power of an odd <\/span>prime<\/a> number.<\/a>[2][3][4] A <\/span>generator <\/a>of this cyclic group is called a primitive root\u00a0<\/span>modulo <\/span>n<\/em>,[5] <\/a>or a primitive element of Z<\/span>n<\/em>\u00d7.The order of (i.e., the number of elements in) Z<\/span>n<\/em>\u00d7 is given by <\/span>Euler's totient function <\/a>\u03c6<\/em>(<\/span>n<\/em>). (sequence <\/span>A000010 <\/a>in\u00a0<\/span>the <\/span>OEIS) <\/a>Euler's theorem <\/a>says that <\/span>a<\/em>\u03c6<\/em>(<\/span>n<\/em>) \u2261 1 (mod <\/span>n<\/em>) for every <\/span>a<\/em>coprime to <\/span>n<\/em>; the\u00a0<\/span>lowest power of <\/span>a<\/em> which is congruent to 1 modulo <\/span>n<\/em> is called the <\/span>multiplicative\u00a0<\/a>order <\/a>of <\/span>a<\/em> modulo <\/span>n<\/em>. In particular, for <\/span>a<\/em> to be a primitive root modulo <\/span>n<\/em>, <\/span>\u03c6<\/em>(<\/span>n<\/em>) has to be\u00a0<\/span>the smallest power of <\/span>a<\/em> which is congruent to 1 modulo <\/span>n<\/em>.\u00a0<\/span>For example, if <\/span>n<\/em> = 14 then the elements of <\/span>Z<\/strong>n<\/em>\u00d7 are the congruence classes {1, 3, 5, 9, 11, 13}; there are <\/span>\u03c6<\/em>(14) = 6 of them. Here is a table of their powers modulo 14:<\/span>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14.<\/p>\r\n \r\n\r\n \r\n\r\n \r\n\r\n5.7.3 DISCRETE LOGARITHMS<\/strong>\r\n\r\n \r\n\r\n \r\n

In general, let G<\/em> be any group, with its group operation denoted by multiplication. Let b<\/em> and g<\/em> be any elements of G<\/em>. Then any integer k<\/em> that solves b<\/em>k<\/em> = g<\/em> is termed a discrete logarithm (or simply logarithm, in this context) of g<\/em> to the base b<\/em>. We write k<\/em> = logb<\/em> g<\/em>. Depending on b<\/em> and g<\/em>, it is possible that no discrete logarithm exists, or that more than one discrete logarithm exists. Let H<\/em> be\u00a0the <\/span>subgroup <\/a>of <\/span>G<\/em> generated <\/a>by <\/span>b<\/em>. Then <\/span>H<\/em> is a <\/span>cyclic group, <\/a>and integral log<\/span>b<\/em> g<\/em> exists for all <\/span>g<\/em> in <\/span>H<\/em>. If <\/span>H<\/em> is infinite, then log<\/span>b<\/em> g<\/em> is also unique, and the discrete logarithm amounts to a <\/span>group isomorphism.<\/a><\/p>\r\n\r\n<\/div>\r\n \r\n\r\nlogb : H ->\u00a0 Z\r\n\r\n \r\n

On the other hand, if H<\/em> is finite of size n<\/em>, then logb<\/em> g<\/em> is unique only up to congruence modulo n<\/em>, and the discrete logarithm amounts to a group isomorphism<\/p>\r\n \r\n\r\nlogb : H\u00a0 -> Zn<\/sub>\r\n\r\n \r\n

where Zn<\/em><\/sub> denotes the ring <\/a>of integers modulo n<\/em>. The familiar base change formula for ordinary logarithms remains valid: If c<\/em> is another generator of H<\/em>, then<\/p>\r\n \r\n

logc(g)=logc(b).logb(g)<\/p>\r\n \r\n\r\n \r\n\r\n \r\n\r\nSummary<\/strong>\r\n\r\n\u00d8 Outlined the concept of number theory\r\n\r\n\u00d8 Discussed the integer division\r\n\r\n\u00d8 Explained the about the divisibility properties\r\n\r\n\u00d8 Introduction to prime numbers and relative prime number\r\n\r\n\u00d8 Explored the various examples of GCD.\r\n\r\n\r\n\r\n\r\n
you can view video on Number Theory<\/strong><\/td>\r\n\"\"<\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n\"\"\r\n\r\n ","rendered":"
\"epgp<\/a>
\n<\/span><\/div>\n
\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

Learning Objectives<\/strong><\/p>\n

\u00d8\u00a0 To understand the basic exponential and logarithmic functions<\/p>\n

\u00d8\u00a0\u00a0 To understand the basic outline to<\/p>\n

 <\/p>\n

o\u00a0\u00a0 prime numbers<\/p>\n

o\u00a0\u00a0 Primality Testing<\/p>\n

o\u00a0\u00a0 Primitive Roots & Discrete Logarithms<\/p>\n

o\u00a0\u00a0 Euclidean and Extended Euclidean Algorithms.<\/p>\n

 <\/p>\n

 <\/p>\n

5.1 Introduction<\/strong><\/p>\n

 <\/p>\n

Number theory is a branch of pure mathematics <\/a>devoted primarily to the study of integers. <\/a>It is sometimes called “The Queen of Mathematics” because of its foundational place in the discipline. The encryption algorithms depends heavily on modular arithmetic. We need to develop various machinery (notations and techniques) for manipulating numbers before can describe algorithms in a natural fashion.First we start with divisors.<\/p>\n<\/div>\n

 <\/p>\n

\n

5.2 Set of Integers<\/strong><\/p>\n

 <\/p>\n

The set of integers, denoted by Z, contains all integral numbers (with no fraction) from negative infinity to positive infinity. The integers are made up of positive numbers, negative numbers and zero. The positive numbers are like the naturals, but with a “plus” before:+1, +2, +3 \u2026.. Nevertheless, the “plus” of the positive numbers does not need to be be written. On the other hand, the negative numbers are like the naturals but with a “minus” before:-1,-2,-3\u2026. The number zero is special, because it is the only one that has neither a plus nor a minus, showing that it is neither positive nor negative. For example, the following numbers are integers:<\/p>\n

 <\/p>\n

 <\/p>\n

Z = {\u2026..,-3,-2,-1,0,1,2,3,\u2026..}<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

5.3 Binary Operations<\/strong><\/p>\n

 <\/p>\n

In cryptography, we are interested in three binary operations applied to the set of integers. A binary operation takes two inputs and creates one output. A binary operation on A is a rule that assigns to every pair of elements of A a unique element of A.<\/p>\n

 <\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

 <\/p>\n<\/div>\n

 <\/p>\n

\n

5.4 Integer Division<\/strong><\/p>\n

 <\/p>\n

\u00d8\u00a0 In integer arithmetic, if we divide a by n, we can get q and r . The relationship between these four integers can be shown as<\/p>\n

 <\/p>\n

a = q \u00d7 n + r<\/strong><\/p>\n

 <\/p>\n

\u00d8\u00a0 Assume that a = 255 and n = 11. We can find q = 23 and R = 2 using the division algorithm.<\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

5.4.1 Integer Division Properties<\/strong><\/p>\n

 <\/p>\n

\u00d8\u00a0 Property 1: if a\\1, then a=+\/- 1.<\/p>\n

\u00d8\u00a0\u00a0 Property 2: if a\\b and b\\a, then a=+\/-b.<\/p>\n

\u00d8\u00a0\u00a0 Property 3: if a\\b and b\\c, then a\\c.<\/p>\n

\u00d8\u00a0\u00a0 Property 4: if a\\b and a\\c, then a\\(m*b+n*c), where m and n are arbitrary integers.<\/p>\n<\/div>\n

 <\/p>\n

\n

\u00a0 \u00a0 5.5 Divisors<\/strong><\/p>\n

 <\/p>\n

5.5.1<\/strong>\u00a0\u00a0\u00a0\u00a0 Definition<\/strong><\/p>\n

 <\/p>\n

Let a, b and c be integers such that<\/p>\n

a = b \u00b7c<\/p>\n

 <\/p>\n

Then b and c are said to divide (or are factors) of a, while a is said to be a multiple of b (as well as of c). The pipe symbol \u201c|\u201d denotes \u201cdivides\u201d so the situation is summarized by:<\/p>\n

 <\/p>\n

b | a\u00a0\u00a0\u00a0\u00a0^ \u00a0 c | a<\/p>\n

 <\/p>\n

5.5.2<\/strong>\u00a0\u00a0\u00a0\u00a0 Examples<\/strong><\/p>\n

 <\/p>\n

Which of the following is true?<\/p>\n

 <\/p>\n

1.\u00a0 77 | 7<\/p>\n

2.\u00a0 7 | 77<\/p>\n

3.\u00a0 24 | 24<\/p>\n

4.\u00a0 0 | 24<\/p>\n

5.\u00a0 24 | 0<\/p>\n

 <\/p>\n

Answer:<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 77 | 7: false bigger number can\u2019t divide smaller positive number<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 7 | 77: true because 77 = 7 \u00b7<\/em> 11<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 24 | 24: true because 24 = 24 \u00b7<\/em> 1<\/p>\n

4.\u00a0\u00a0\u00a0\u00a0\u00a0 0 | 24: false, only 0 is divisible by 0<\/p>\n

5.\u00a0\u00a0\u00a0\u00a0\u00a0 24 | 0: true, 0 is divisible by every number (0 = 24 \u00b7<\/em> 0)<\/p>\n

 <\/p>\n

5.5.3 Facts<\/strong><\/p>\n

 <\/p>\n

Fact 1: The integer 1 has only one divisor, itself.<\/p>\n

Fact 2: Any positive integer has at least two divisors.1 and itself(but it can have more)<\/p>\n<\/div>\n

 <\/p>\n

\n

5.6 GCD<\/strong><\/p>\n

 <\/p>\n

The greatest common divisor of two positive integers is the largest integer that can divide both integers.\u00a0\u00a0\u00a0\u00a0 When gcd (a, b) = 1, we say that a and b are relatively prime.<\/p>\n

 <\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

5.6.1 Relatively Prime Numbers & GCD<\/strong><\/p>\n

 <\/p>\n

\u2022\u00a0 Two numbers a,b are relatively prime (co prime) if they have no common divisors apart from 1<\/p>\n

 <\/p>\n

eg. 8 and 15 are relatively prime since factors of 8 are 1,2,4,8 and of 15 are 1, 3, 5,15 and 1 is the only common factor<\/p>\n

 <\/p>\n

\u2022\u00a0\u00a0 Conversely can determine the greatest common divisor by comparing their prime factorizations and using least powers<\/p>\n

 <\/p>\n

eg. 300 = 2^1×3^1×5^2 ; 18<\/p>\n

=\u00a0\u00a0 2^1×3^2 hence GCD(18,300)<\/p>\n

=\u00a0\u00a0 2^1×3^1×5^0 = 6<\/p>\n<\/div>\n

\n

5.6.2 GCD Example<\/strong><\/p>\n

 <\/p>\n

Find the greatest common divisor of 140 and 12.<\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

5.6.3 GCD using Extended Euclidean Algorithm<\/strong><\/p>\n

 <\/p>\n

Given two integers a and b, we often need to find other two integers, s and t, such that<\/p>\n

\"\"<\/p>\n<\/div>\n

\n

Example<\/strong><\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

5.7 PRIME NUMBERS<\/strong><\/p>\n

 <\/p>\n

Prime numbers only have divisors of 1 and self \u2013 they cannot be written as a product of other numbers \u2013 note: 1 is Prime, but is generally not of interest<\/p>\n

 <\/p>\n

\u2022\u00a0 Eg. 2,3,5,7 are prime, 4, 6, 8,9,10 are not<\/p>\n

\u2022\u00a0\u00a0 Prime numbers are central to number theory<\/p>\n

\u2022\u00a0 List of prime number less than 200 is: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53<\/p>\n

59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163<\/p>\n

167 173 179 181 191 193 197 199<\/p>\n

 <\/p>\n

5.7.1 PRIME FACTORIZATION<\/strong><\/p>\n

 <\/p>\n

\u2022\u00a0\u00a0 Let us factorize the any number n: n = a x b x c<\/p>\n

\u2022\u00a0\u00a0 Factoring a number is relatively hard compared to multiplying the factors together to generate the number<\/p>\n

\u2022\u00a0 The prime factorisation of a number n is when its written as a product of primes \u2013 eg. 91 = 7 x 13; 3600 = 2^4 x 3^2 x 5^2<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

5.7.2 PRIMITIVE ROOTS<\/strong><\/p>\n

 <\/p>\n

 <\/p>\n

If n<\/em> is a positive integer, the integers between 1 and n<\/em> \u2212 1 that are coprime <\/a>to n<\/em> (or equivalently, the congruence classes <\/a>coprime to n<\/em>) form a group <\/a>with multiplication modulo <\/a>n<\/em> as the operation; it is denoted by Zn<\/em>\u00d7 <\/a>and is called the group\u00a0<\/a>of units <\/a>modulo <\/span>n<\/em> or the group of primitive classes modulo <\/span>n<\/em>. As explained in the article <\/span>multiplicative group of integers modulo n<\/em>, <\/a>this group is <\/span>cyclic <\/a>if and only if <\/span>n<\/em> is equal to 2, 4, <\/span>p<\/em>k<\/em>, or 2<\/span>p<\/em>k<\/em> where <\/span>p<\/em>k<\/em> is a power of an odd <\/span>prime<\/a> number.<\/a>[2][3][4] A <\/span>generator <\/a>of this cyclic group is called a primitive root\u00a0<\/span>modulo <\/span>n<\/em>,[5] <\/a>or a primitive element of Z<\/span>n<\/em>\u00d7.The order of (i.e., the number of elements in) Z<\/span>n<\/em>\u00d7 is given by <\/span>Euler’s totient function <\/a>\u03c6<\/em>(<\/span>n<\/em>). (sequence <\/span>A000010 <\/a>in\u00a0<\/span>the <\/span>OEIS) <\/a>Euler’s theorem <\/a>says that <\/span>a<\/em>\u03c6<\/em>(<\/span>n<\/em>) \u2261 1 (mod <\/span>n<\/em>) for every <\/span>a<\/em>coprime to <\/span>n<\/em>; the\u00a0<\/span>lowest power of <\/span>a<\/em> which is congruent to 1 modulo <\/span>n<\/em> is called the <\/span>multiplicative\u00a0<\/a>order <\/a>of <\/span>a<\/em> modulo <\/span>n<\/em>. In particular, for <\/span>a<\/em> to be a primitive root modulo <\/span>n<\/em>, <\/span>\u03c6<\/em>(<\/span>n<\/em>) has to be\u00a0<\/span>the smallest power of <\/span>a<\/em> which is congruent to 1 modulo <\/span>n<\/em>.\u00a0<\/span>For example, if <\/span>n<\/em> = 14 then the elements of <\/span>Z<\/strong>n<\/em>\u00d7 are the congruence classes {1, 3, 5, 9, 11, 13}; there are <\/span>\u03c6<\/em>(14) = 6 of them. Here is a table of their powers modulo 14:<\/span><\/p>\n<\/div>\n

\n

\"\"<\/p>\n

 <\/p>\n

 <\/p>\n

The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14.<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

5.7.3 DISCRETE LOGARITHMS<\/strong><\/p>\n

 <\/p>\n

 <\/p>\n

In general, let G<\/em> be any group, with its group operation denoted by multiplication. Let b<\/em> and g<\/em> be any elements of G<\/em>. Then any integer k<\/em> that solves b<\/em>k<\/em> = g<\/em> is termed a discrete logarithm (or simply logarithm, in this context) of g<\/em> to the base b<\/em>. We write k<\/em> = logb<\/em> g<\/em>. Depending on b<\/em> and g<\/em>, it is possible that no discrete logarithm exists, or that more than one discrete logarithm exists. Let H<\/em> be\u00a0the <\/span>subgroup <\/a>of <\/span>G<\/em> generated <\/a>by <\/span>b<\/em>. Then <\/span>H<\/em> is a <\/span>cyclic group, <\/a>and integral log<\/span>b<\/em> g<\/em> exists for all <\/span>g<\/em> in <\/span>H<\/em>. If <\/span>H<\/em> is infinite, then log<\/span>b<\/em> g<\/em> is also unique, and the discrete logarithm amounts to a <\/span>group isomorphism.<\/a><\/p>\n<\/div>\n

 <\/p>\n

logb : H ->\u00a0 Z<\/p>\n

 <\/p>\n

On the other hand, if H<\/em> is finite of size n<\/em>, then logb<\/em> g<\/em> is unique only up to congruence modulo n<\/em>, and the discrete logarithm amounts to a group isomorphism<\/p>\n

 <\/p>\n

logb : H\u00a0 -> Zn<\/sub><\/p>\n

 <\/p>\n

where Zn<\/em><\/sub> denotes the ring <\/a>of integers modulo n<\/em>. The familiar base change formula for ordinary logarithms remains valid: If c<\/em> is another generator of H<\/em>, then<\/p>\n

 <\/p>\n

logc(g)=logc(b).logb(g)<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

Summary<\/strong><\/p>\n

\u00d8 Outlined the concept of number theory<\/p>\n

\u00d8 Discussed the integer division<\/p>\n

\u00d8 Explained the about the divisibility properties<\/p>\n

\u00d8 Introduction to prime numbers and relative prime number<\/p>\n

\u00d8 Explored the various examples of GCD.<\/p>\n\n\n\n
you can view video on Number Theory<\/strong><\/td>\n\"\"<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\"\"<\/p>\n

 <\/p>\n","protected":false},"author":3,"menu_order":4,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-kulothungan"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-54","chapter","type-chapter","status-publish","hentry","contributor-dr-kulothungan"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/54","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":6,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/54\/revisions"}],"predecessor-version":[{"id":528,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/54\/revisions\/528"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/54\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/media?parent=54"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapter-type?post=54"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/contributor?post=54"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/license?post=54"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}