Question

In: Computer Science

[PYTHON] Two natural number p,q are called coprime if there are no common prime factors in...

[PYTHON] Two natural number p,q are called coprime if there are no common prime factors in their prime factorization. E.g. 15 and 20 are not coprime because 5 is a common prime number in their prime factorization, while 20 and 9 are coprime. The Euler’s phi function, φ(n), counts the number of all natural numbers ≤ n which are coprime to n. E.g. φ(9) = 6, as all natural numbers ≤ 9 are 1,2,3,4,5,6,7,8,9. And out of these, the numbers coprime to 9 are 1,2,4,5,7 and 8, a total of 6 natural numbers.

You are required to write a Python function totient(n) that accepts a natural number as input argument and returns the following:

1. a list of all the natural numbers less than or equal to n which are coprime to n; and

2. the result of the Euler’s phi function when run on n.

E.g. totient(9) should return [1,2,4,5,7,8], 6

You can use your function prime factors from Problem 2. to determine if two numbers are coprime or not.

Solutions

Expert Solution

#source code:

def prime_factor_gcd(value,num):
   if(value==0):
       return num
   else:
       return prime_factor_gcd(num%value,value)
def Totient(n):
   totient_list=[]
   sum=0
   for i in range(1, n):
       if(prime_factor_gcd(i,n)==1):
           totient_list.append(i)
           sum+=1
   return totient_list,sum
num=int(input("Enter natural number:"))
list,count=Totient(num)
print("totient({}):{},{}".format(num,list,count))

#output:

#if you have any doubt comment below...


Related Solutions

Java program Prime Numbers A prime number is a natural number which has exactly two distinct...
Java program Prime Numbers A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5 and 7. Write a java program which reads a list of N integers and prints the number of prime numbers in the list. Input: The first line contains an integer N, the number of elements in the list. N numbers are given in the following lines. Output:...
A prime number (or prime) is a natural number greater than 1 that has no posítive...
A prime number (or prime) is a natural number greater than 1 that has no posítive divisors other than 1 and itself. Write a Python program which takes a set of positive numbers from the input and returns the sum of the prime numbers in the given set. The sequence will be ended with a negative number.
Given the prime factors p and​ q, the encryption exponent​ e, and the ciphertext​ C, apply...
Given the prime factors p and​ q, the encryption exponent​ e, and the ciphertext​ C, apply the RSA algorithm to find ​(a) the decryption exponent d and ​(b) the plaintext message M. p q e C 17 5 19 65 I have to get d and M
use Python The assertion that every even number is the sum of two prime numbers is...
use Python The assertion that every even number is the sum of two prime numbers is called Goldbach’s conjecture. You will write a program that asks the user for an integer number, then checks if the integer is even, and finally determines two prime numbers that sum to the user’s entered integer number. Assignment Requirements Three functions are required: get_input(): This function takes no parameters, but will ask the user for an integer number. It will return a valid integer....
Let p and q be any two distinct prime numbers and define the relation a R...
Let p and q be any two distinct prime numbers and define the relation a R b on integers a,b by: a R b iff b-a is divisible by both p and q. For this relation R: Prove that R is an equivalence relation. you may use the following lemma: If p is prime and p|mn, then p|m or p|n. Indicate in your proof the step(s) for which you invoke this lemma.
For p a given prime number, define the p-adic norm | * |p as follows on...
For p a given prime number, define the p-adic norm | * |p as follows on Q: Given q in Q, we can write it as a product q = (p^m)(a/b) with a,b integers which are not divisible by p, and m an integer which is uniquely determined by q (check that m is indeed uniquely determined by q). Then define |q|p = p^(-m). Check that Q with distance dp(q1,q2) = |q1 - q2|p is a metric space (here q1-q2...
2. (a) Let p be a prime. Determine the number of elements of order p in...
2. (a) Let p be a prime. Determine the number of elements of order p in Zp^2 ⊕ Zp^2 . (b) Determine the number of subgroups of of Zp^2 ⊕ Zp^2 which are isomorphic to Zp^2 .
Let q and p be natural numbers, and show that the metric on Rq+p is equivalent...
Let q and p be natural numbers, and show that the metric on Rq+p is equivalent to the metric it has if we identify Rq+p with Rq × Rp.
Python question Recall that a prime number is an integer that is only divisible by 1...
Python question Recall that a prime number is an integer that is only divisible by 1 and itself. For example, numbers 2, 3, 5, 7, 13, 19 are prime, whereas 4, 10, 12, 100 are not. Also, recall that factors are the numbers you multiply to get another number. For example, 24 has 8 factors: 1, 2, 3, 4, 6, 8, 12, and 24. As you know, any number can be factorized into several (possibly repeating) prime factors. For instance,...
The ‘Exclusive OR’ operation (also called XOR) between two propositions p and q is defined as...
The ‘Exclusive OR’ operation (also called XOR) between two propositions p and q is defined as follows: p ⊕ q = (p ∨ q) ∧ ¬(p ∧ q) Using laws of propositional logic prove the following: (i.) Exclusive OR is commutative, i.e., p ⊕ q ≡ q ⊕ p. (ii.) p ⊕ p is a contradiction. (iii.) Conjunction distributes over Exclusive OR, i.e, for any proposition r, r ∧ (p ⊕ q) ≡ (r ∧ p) ⊕ (r ∧ q)....
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT