-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path64. There are no primitive roots modulo 2^n!!.py
More file actions
53 lines (40 loc) · 1.11 KB
/
Copy path64. There are no primitive roots modulo 2^n!!.py
File metadata and controls
53 lines (40 loc) · 1.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def there_are_no_primitive_roots_mod_2_n_factorial(n):
"""
Checks if there are no primitive roots modulo 2^n!!.
Args:
n: The exponent.
Returns:
True if there are no primitive roots modulo 2^n!!, False otherwise.
"""
# Check if n is a positive integer.
if n <= 0:
return False
# Check if 2^n!! is an odd integer.
if 2**n != 2**n % 2:
return False
# Check if there are no primitive roots modulo 2^n!!.
for i in range(2, 2**n + 1):
if is_primitive_root(i, 2**n):
return False
return True
def is_primitive_root(a, n):
"""
Checks if the integer a is a primitive root modulo n.
Args:
a: The integer.
n: The modulus.
Returns:
True if the integer a is a primitive root modulo n, False otherwise.
"""
# Check if a is an integer greater than 1 and less than n.
if a <= 1 or a >= n:
return False
# Check if the order of a modulo n is n - 1.
order_of_a = order_of_integer(a, n)
if order_of_a != n - 1:
return False
# Check if a is a primitive root modulo n.
for i in range(2, n):
if pow(a, i) % n == 1:
return False
return True