20071127, 18:01  #1 
Nov 2007
home
5^{2} Posts 
checking cyclic group belongingness of an element
How do I check if some element was generated by some base. For example if the base is 2 and modulus is 7 the elements that are generated are {1,2,4} while elements that are not generated are {3,5,6,0}. Is there some test to check if some element like {4 or 5} was really generated by 2 or not? I tried googling this but did not find anything, probably because the phrasing of the question is incorrect.

20071129, 16:56  #2  
Feb 2007
2^{4}·3^{3} Posts 
Quote:
There is the notion of the multiplicative order of an element, ord(x,n) = # { x^i mod n ; i=0,1,... } (well if we have an element of a finite group we know that we will get sooner or later the neutral element of the group) I don't think there is an explicit formula not even for ord(x,n) ; and I fear that it's not simple to find the answer to your problem in the general case. In some cases you may know, e.g. if x is invertible in Z/nZ then you can only get invertible elements (relatively prime to n) and no divisors of zero (having a common divisor > 1 with n) If n is prime, all nonzero elements are invertible and they will never give 0. If (Z/nZ)* is monogenic (thus cyclic) then any of the generators gives any other element. If the order of an element does not divide the order of the "base", it cannot be written as a power of that base. etc. PS: even, I think that the LLtest amounts just to know if some element can be written as a power of another one (once the procedure is rewritten in some "twisted" way), so if there were a simple general solution, you knew about primality without doing the p 1(?) squarings. Last fiddled with by m_f_h on 20071129 at 17:09 

20071130, 07:42  #3 
Aug 2002
Ann Arbor, MI
661_{8} Posts 
Looking up stuff on Primitive Roots is probably as close as you'll get to a solution.

20071130, 11:02  #4 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
You want to know if there is a k so that b^{[I]k[/I]} ≡ a (mod p), where b is your base, a is the element whose "belongingness" you want to check and p is the modulus.
The order of a power is ord(b^{[I]k[/I]}) = ord(b)/gcd(ord(b),k), so the order of the power will divide the order of b. Hence we obviously need ord(a)ord(b) to have a solution. Since your group (Z/pZ)* is cyclic, let g be a generator and write a = g^{[I]n[/I]}, b = g^{[I]m[/I]}. We want b^{[I]k[/I]} = (g^{[I]m[/I]})^{[I]k[/I]} = g^{[I]mk[/I]} = a = g^{[I]n[/I]}, hence mk ≡ n (mod p1). This has a solution in k if gcd(m, p1)  gcd(n, p1), and since ord(b) = (p1)/gcd(m, p1) (likewise for a) we have (p1)/ord(b)  (p1)/ord(a) which is equivalent to ord(a)ord(b). Hence ord(a)ord(b) is a necessary and sufficient condition that there is a k so that b^{[I]k[/I]} = a in a cyclic group. Alex Edit: to compute ord(a) and ord(b) in (Z/pZ)* efficiently you'll need the factorisation of p1 of course. Last fiddled with by akruppa on 20071130 at 11:04 
20071130, 13:18  #5 
Nov 2007
home
5^{2} Posts 
"Hence ord(a)ord(b) is a necessary and sufficient condition that there is a k so that bk = a in a cyclic group."
So, in other words, if the order of the element is greater than the order of the base then the element can't be generated by the base. 
20071130, 13:25  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Yes, that follows from my statement, but it is not equivalent.
Alex 
20071130, 13:26  #7  
"Bob Silverman"
Nov 2003
North of Boston
1110101001000_{2} Posts 
Quote:
Your statement is a corollary, but is not equivalent 'in other words'. 

20071202, 02:40  #8 
Nov 2007
home
11001_{2} Posts 
Yeah I realized this couple of minutes after posting. A correct simplification is that ord(b) must be divisible ord(a) without leaving a remainder.
Anyway it turned out that this did not help me solve that problem I was working on. I was trying to find a way to transform base1^x mod p problem into a base2^x mod p problem, where base2 has a higher order than base1. This transform is easy if the order of the base1 and base2 are the same and base2 is unspecified. All you have to do is take a valid kth root of the base1 and the element. This way the exponent remains the same. However if you are trying to change the nonprimitive base1 to any primitive base2 this transform can only be valid for exponents that are less than the order of base1. So far I can't figure out how to do this. 
20071202, 08:28  #9  
"Nancy"
Aug 2002
Alexandria
9A3_{16} Posts 
Quote:
Quote:
Alex 

20071202, 10:26  #10 
Nov 2007
home
5^{2} Posts 
3^4 mod 11=5; ord(3)=5;
3rd root inverting exponent= 3*exponent=1 mod 5, inverting exponent=2; so (3^2)^4 =5^2 mod 11; therefore 9^x = 3 mod 11; and 3^x = 5 mod 11; also ord(9)=5; So base 3 is changed to base 9, exponent is kept the same and the element is modified. However it does not seem possible transform a nonprimitive base to any primitive base. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Cyclic fields with class number h  carpetpool  Abstract Algebra & Algebraic Number Theory  0  20180130 06:10 
Cyclic Group Problem  davar55  Homework Help  67  20170523 13:16 
Round Off Checking and Sum (Inputs) Error Checking  Forceman  Software  2  20130130 17:32 
Name That Element  Flatlander  Lounge  24  20090821 16:53 
Number of nelement permutations with exactly k inversions  tytus  Math  3  20050204 10:10 