Question

Given the values of n below, determine, without exhaustive search, etc., how many integers k there are, with gcd(k,n)=1, and 1≤k≤n, such that k has a square root modulo n. Perform this for:

(a) n=143

(b) n=286

(c) n=572

(d) n=1144

(e) n=2288

Answer 1

The number of integers k satisfying the given conditions can be determined by analyzing the prime factorization of n and applying the formulas based on q, the number of distinct primes in the prime factorization.

Step-by-step explanation:

To determine the number of integers k, with gcd(k,n)=1, and 1≤k≤n, such that k has a square root modulo n, we need to analyze the prime factorization of n. If n is a product of distinct primes raised to an odd power, then the number of such integers k is 2q, where q is the number of distinct primes in the prime factorization of n.

If n is a product of distinct primes raised to an even power, then the number of such integers k is 2q-1, where q is the number of distinct primes in the prime factorization of n.

(a) For n=143, the prime factorization is 11*13. Therefore, q=2 and the number of integers k is 22-1=2.

(b) For n=286, the prime factorization is 2*11*13. Therefore, q=3 and the number of integers k is 23-1=4.

(c) For n=572, the prime factorization is 22*11*13. Therefore, q=3 and the number of integers k is 23-1=4.

(d) For n=1144, the prime factorization is 23*11*13. Therefore, q=3 and the number of integers k is 23-1=4.

(e) For n=2288, the prime factorization is 24*11*13. Therefore, q=3 and the number of integers k is 23-1=4.