A254328 -id:A254328 - cp's OEIS frontend

A303704 Numbers k such that all coprime quadratic residues modulo k are squares.

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

Offset: 1

Jianing Song, Apr 29 2018

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)

			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.

Cf. A046073, A057828, A214583.

A254328 is a subsequence.

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

A306271 a(n) is the smallest positive integer x such that x^2 mod n is a square, with x^2 >= n.

Original entry on oeis.org

1, 2, 2, 2, 3, 4, 5, 3, 3, 7, 8, 4, 10, 11, 4, 4, 13, 6, 15, 6, 5, 18, 19, 5, 5, 21, 6, 9, 24, 8, 26, 6, 7, 29, 6, 6, 31, 32, 8, 7, 35, 10, 37, 16, 7, 40, 41, 7, 7, 10, 10, 19, 46, 12, 8, 9, 14, 51, 52, 8, 54, 55, 8, 8, 9, 14, 59, 26, 16, 12, 63, 9, 65, 66, 10

Offset: 1

Daniel Suteu, Feb 01 2019

nonn

			For n = 10, a(10) = 7, which is the smallest positive integer x such that x^2 mod n is a square and that x^2 >= n. Here 7^2 mod 10 = 9 = 3^2.

Daniel Suteu, Table of n, a(n) for n = 1..10000
Wikipedia, Congruence of squares

Cf. A000290, A048152, A062803, A112045, A254328, A306257.

a:= proc(n) local k, t;
      for k do t:= irem(k^2, n);
        if issqr(t) and isqrt(t)<>k then break fi
      od; k
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 01 2019

a[n_] := For[x = Sqrt[n]//Ceiling, True, x++, If[IntegerQ[Sqrt[PowerMod[x, 2, n]]], Return[x]]];
Array[a, 100] (* Jean-François Alcover, Nov 07 2020 *)

a(n) = for(k=sqrtint(n), oo, if(issquare(k^2 % n) && sqrtint(k^2 % n) != k, return(k)));

a(n^2) = n.

a(p) = p - floor(sqrt(p)), for prime p > 2.

A330404 Least nonsquare k that is a quadratic residue modulo n.

Original entry on oeis.org

2, 2, 3, 5, 5, 3, 2, 8, 7, 5, 3, 12, 3, 2, 6, 17, 2, 7, 5, 5, 7, 3, 2, 12, 6, 3, 7, 8, 5, 6, 2, 17, 3, 2, 11, 13, 3, 5, 3, 20, 2, 7, 6, 5, 10, 2, 2, 33, 2, 6, 13, 12, 6, 7, 5, 8, 6, 5, 3, 21, 3, 2, 7, 17, 10, 3, 6, 8, 3, 11, 2, 28, 2, 3, 6, 5, 11, 3, 2, 20, 7, 2, 3, 21

Offset: 1

Jianing Song, Dec 14 2019

nonn

a(n) >= n if and only if n is in A254328.

It seems that lim_{n->oo} a(n)/n = 0. Conjectured last term m such that a(m)/m >= 1/k, k = 1, 2, 3, ...: 16, 48, 240, 288, 720, 720, 720, 720, 1008, 1440, ...

			k is a quadratic residue modulo 16 if and only if k == 0, 1, 4, 9 (mod 16). Since 0, 1, 4, 9 and 16 are squares, a(16) = 17.
k is a quadratic residue modulo 48 if and only if k == 0, 1, 4, 9, 16, 25, 33, 36 (mod 48). Since 0, 1, 4, 9, 16 and 25 are squares, a(48) = 33.
k is a quadratic residue modulo 720 if and only if k == 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 145, ..., 676 (mod 720). Since 0, 1, 4, ..., 144 are squares, a(720) = 145.

Jianing Song, Table of n, a(n) for n = 1..10000

A309680 is an alternate version.

Cf. A254328, A330423.

a(n) = my(k=1); while(!issquare(Mod(k,n)) || issquare(k), k++); k

A254329 Numbers n such that all x^2 mod n are prime powers (including 0 and 1).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 20, 32

Offset: 1

Joerg Arndt, Jan 28 2015

Cf. A065428, A254328.

f[n_] := Mod[Range[n]^2, n]; Select[Range@ 10000, AllTrue[f@ #, Length@ FactorInteger[#] == 1 &] &] (* AllTrue function introduced with Version 10; Michael De Vlieger, Jan 29 2015 *)

is(n)=for(i=2,9,if(!isprimepower(i^2%n) && i^2%n>1, return(0))); 1 \\ Charles R Greathouse IV, Jan 30 2015

cp's OEIS Frontend

A303704 Numbers k such that all coprime quadratic residues modulo k are squares.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A306271 a(n) is the smallest positive integer x such that x^2 mod n is a square, with x^2 >= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A330404 Least nonsquare k that is a quadratic residue modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A254329 Numbers n such that all x^2 mod n are prime powers (including 0 and 1).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI