OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / 1st lecture in Primitive roots and indices

1st lecture in Primitive roots and indices

Definition of the order of an integer modulo n: Let n > 1 and gcd(a, n) = 1. The order of a modulo n is the smallest positive integer k such that ak ≡ 1 (mod n).

Theorem: Let the integer a have order k modulo n. Then ab ≡ 1 (mod n) if and only if k|b; in particular, k|?(n)

Proof: Suppose to be begin with k | b, so that h = jk for some integer j. Because     ak ≡ 1 (mod n), this implies that (ak)j ≡ 1j (mod n) or ab ≡ 1 (mod n).

Conversely, let b be any positive integer satisfying ab ≡ 1 (mod n). By division algorithm, there exist q and r such that b = qk + r, where 0 ≤ r < k. Consequently,

ab = aqk + r = (ak)r ar

By hypothesis, both ab ≡ 1 (mod n) and ak ≡ 1 (mod n), the implication of which is that ar ≡ 1 (mod n). Because 0 ≤ r < k, we end up with r = 0; otherwise, the choice of k as the smallest positive integer such that ak ≡ 1 (mod n) is contradicted. Hence, h = qk, and k | b.

Theorem: If the integer a has order k modulo n, then ai ≡ aj (mod n) if and only if   i ≡ j (mod n).

Proof: First, suppose that ai ≡ aj (mod n), where i ≥ j. Because a is relatively prime to n, we may cancel a power of a to obtain ai – j ≡ 1 (mod n). According to previous theorem, this last congruence holds only if k | i – j , which just another way of saying that i ≡ j (mod k).

Conversely, let i ≡ j(mod k). Then we have i = j + qk for some integer q. By the condition k, ak ≡ 1 (mod n), so that

ai ≡ aj + qk ≡ aj (ak)q ≡ aj (mod n).

Theorem: If the integer a has order k modulo n and b > 0, then ab has order

k /gcd(b, k).

Proof: Let d = gcd(b, k). Then we may write b = b1d and k = k1d with gcd            (b1, k1)=1. Clearly, (ab)k1= (ab1k)k / d = (ak)b1 ≡ 1 (mod n)

If ab is assume to have order r modulo n, then r | k1. On the other hand, since a has order k modulo n, the congruence ahr ≡ (ah)r ≡ 1 (mod n)

Indicates that k | br; in words k1d | h1dr or k1 |b1r. But gcd(k1, b1) = 1, and therefore k1 | r. This divisibility relation, when combined with the one obtained earlier gives

r = k1 = k /d = k/gcd(h, k). (proved).

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *