The number of integers k with gcd(k, n) = 1 and 1 <= k <= n that have a square root modulo n varies depending on the value of n. For n = 143, there is only one such integer, while for n = 286, there are four, for n = 572, there are two, for n = 1144, there are eight, and for n = 2288, there are 16.
(a) n = 143
To determine the number of integers k with gcd(k, 143) = 1 and 1 <= k <= 143 that have a square root modulo 143, we can first find the totient of 143, denoted by φ(143).
φ(143) = (143 - 1)(1 - 1/143) = 140
This means that there are 140 reduced residue classes modulo 143.
To determine the number of integers k with gcd(k, 143) = 1 and 1 <= k <= 143 that have a square root modulo 143, we need to determine how many of these reduced residue classes have a square root modulo 143.
Note that an integer k has a square root modulo n if and only if k^2 ≡ 1 . This means that we only need to consider the squares of the integers modulo 143.
We can calculate the squares of the integers modulo 143 and check if any of them are congruent to 1 (mod 143). The squares are:
1^2 ≡ 1 (mod 143)
2^2 ≡ 4 (mod 143)
3^2 ≡ 9 (mod 143)
142^2 ≡ 9801 (mod 143)
We can see that only 1^2 ≡ 1 (mod 143). This means that there is only one reduced residue class modulo 143 that has a square root modulo 143.
Therefore, there is only one integer k with gcd(k, 143) = 1 and 1 <= k <= 143 that has a square root modulo 143.
(b) n = 286
φ(286) = (286 - 1)(1 - 1/286) = 284
This means that there are 284 reduced residue classes modulo 286.
Calculating the squares of the integers modulo 286 and checking if any of them are congruent to 1 (mod 286), we find that there are four reduced residue classes modulo 286 that have a square root modulo 286: 1^2, 271^2, 273^2, and 283^2.
Therefore, there are four integers k with gcd(k, 286) = 1 and 1 <= k <= 286 that have a square root modulo 286.
(c) n = 572
φ(572) = (572 - 1)(1 - 1/572) = 570
This means that there are 570 reduced residue classes modulo 572.
Calculating the squares of the integers modulo 572 and checking if any of them are congruent to 1 (mod 572), we find that there are two reduced residue classes modulo 572 that have a square root modulo 572: 1^2 and 287^2.
Therefore, there are two integers k with gcd(k, 572) = 1 and 1 <= k <= 572 that have a square root modulo 572.
(d) n = 1144
φ(1144) = (1144 - 1)(1 - 1/1144) = 1142
This means that there are 1142 reduced residue classes modulo 1144.
Calculating the squares of the integers modulo 1144 and checking if any of them are congruent to 1 (mod 1144), we find that there are eight reduced residue classes modulo 1144 that have a square root modulo 1144.
Therefore, there are eight integers k with gcd(k, 1144) = 1 and 1 <= k <= 1144 that have a square root modulo 1144.
(e) n = 2288
φ(2288) = (2288 - 1)(1 - 1/2288) = 2286
This means that there are 2286 reduced residue classes modulo 2288.