login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A303704 Numbers k such that all coprime quadratic residues modulo k are squares. 2
1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 21, 24, 28, 40, 48, 56, 60, 72, 88, 120, 168, 240, 840 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Numbers k such that A046073(k) = A057828(k).

There are exactly 25 members in this sequence and this is the full list. Note that for other k, A046073(k) > A057828(k).

From Jianing Song, Feb 14 2019: (Start)

For the proof that this sequence is finite, we will show that there are no terms > 130729.

Let A(n) = A046073(n) be the number of coprime quadratic residues modulo n. By definition, if k is a term then A(k) <= sqrt(k), that is, A(k)/sqrt(k) <= 1. Let f(n) = A(n)/sqrt(n), then f(n) is multiplicative with f(2) = sqrt(2)/2, f(4) = 1/2, f(2^e) = 2^(e/2 - 3) for e >= 3, f(p^e) = ((p - 1)/2)*p^(e/2 - 1) when p > 2. Note that f(2^e) >= a(2^3), f(p^e) >= f(p), f(p) > 1 when p >= 7. For every number n, we have:

a) if n is divisible by a prime >= 127, then f(n) >= f(2^3)*f(3)*f(5)*f(127) = sqrt(1323/1270) > 1.

b) if n is divisible by two distinct primes >= 23, then f(n) >= f(2^3)*f(3)*f(5)*f(23)*f(29) = sqrt(11858/10005) > 1.

So if k > 130729 is a term, then all prime factors of k are no greater than 113, and k contains at most one prime factor >= 23. On the other hand, if all prime factors of k are no greater than 19, then 53881 is a coprime quadratic residue modulo k because 53881 is a coprime quadratic residue modulo 2^3, 3, 5, 7, 11, 13, 17 and 19, but 53881 is not a perfect square, a contradiction. As a result, k must contain exactly one prime factor p in [23, 113].

Now if a number m is a coprime quadratic residue modulo 2^3, 3, 5, 7, 11, 13, 17, 19 and p, then m is a coprime quadratic residue modulo k. Consider the numbers 53881, 86641, 87481, 102001, 117049 and 130729. At least one of them is a coprime quadratic residue modulo each prime p in [23, 113], so at least one of them is a coprime quadratic residue modulo k, but none of them is a square, a contradiction! (End)

LINKS

Table of n, a(n) for n=1..25.

EXAMPLE

All coprime quadratic residues modulo 21 are 1, 4, 16 and they are all squares, so 21 is a term.

All coprime quadratic residues modulo 840 are 1, 121, 169, 289, 361, 529 and they are all squares, so 840 is a term.

249 == 23^2 is a coprime quadratic residue modulo 280 but 249 is not a square number, so 280 is not a term.

PROG

(PARI) for(k=1, 130729, if(eulerphi(k)/2^#znstar(k)[2]<=sqrt(k), for(j=1, k, if(gcd(j, k)==1&&!issquare(j^2%k), break()); if(j==k, print1(k, ", "))))) \\ Jianing Song, Feb 15 2019

CROSSREFS

Cf. A046073, A057828, A214583.

A254328 is a subsequence.

Sequence in context: A281624 A242441 A064481 * A067939 A067784 A324107

Adjacent sequences:  A303701 A303702 A303703 * A303705 A303706 A303707

KEYWORD

nonn,fini,full

AUTHOR

Jianing Song, Apr 29 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 18:26 EDT 2020. Contains 333116 sequences. (Running on oeis4.)