Determine all natural numbers $n$ such that for each natural number $a$ relatively prime with $n$ and $a \le 1 + \left\lfloor \sqrt{n} \right\rfloor$ there exists some integer $x$ with $a \equiv x^2 \mod n$.

Remark: "Natural numbers" is the set of positive integers.
To determine all natural numbers \( n \) such that for each natural number \( a \) relatively prime with \( n \) and \( a \le 1 + \left\lfloor \sqrt{n} \right\rfloor \), there exists some integer \( x \) with \( a \equiv x^2 \pmod{n} \), we proceed as follows:

1. **Initial Observations**:
   - If \( p^2 \mid n \) and \( n \) works, then so does \( n/p \) for \( p \) an odd prime. Therefore, we restrict our search to numbers not divisible by the square of any odd prime.

2. **Case 1: \( 4 \mid n \)**:
   - Note that \( n = 12 \) is a solution. Now consider \( n > 12 \).
   - A number is a quadratic residue modulo \( 4 \) if it is not \( 3 \pmod{4} \). Hence, \( 3 \) cannot be a quadratic residue, implying \( 3 \mid n \).
   - Since \( 5 \) is not a quadratic residue modulo \( 3 \), we get \( 5 \mid n \) if \( n \ge 16 \). This is easy to verify.
   - Then \( 7 \mid n \) because \( 7 \) is not a square modulo \( 5 \).

3. **Inductive Step**:
   - Suppose the first \( m \) primes \( p_1, p_2, \ldots, p_m \) divide \( n \) and \( 4 \mid n \). Then \( p_{m+1} \mid n \).
   - We prove this by induction on \( m \) with the base case \( m = 4 \).
   - First, observe that \( p_{m+1} \le 1 + \lfloor \sqrt{n} \rfloor \). This can be proven by showing \( 1 + \lfloor \sqrt{n} \rfloor \ge 2 p_m \) and applying Chebyshev's Theorem.
   - Hence, we need \( p_{m+1} \) to be a square modulo \( p_i \) for all primes \( p_i \) below \( p_{m+1} \). Note that \( p_{m+1} \equiv 1 \pmod{4} \), so every odd prime below \( p_{m+1} \) is a square modulo \( p_{m+1} \) by Quadratic Reciprocity. This implies every odd number is a square modulo \( p_{m+1} \). We derive a contradiction because \( 0, 4 \) are also squares. Hence, \( p_{m+1} \mid n \) and we finish our induction.

4. **Conclusion for \( 4 \mid n \)**:
   - This implies every prime divides \( n \), which is false. Hence, no further solutions for \( 4 \mid n \) exist.

5. **Case 2: \( v_2(n) = 1 \)**:
   - If \( v_2(n) = 1 \), then \( n/2 \) works as well. So, we study \( n \) odd.

6. **Odd \( n \)**:
   - \( 2 \) must be a quadratic residue modulo \( n \). Hence, if \( p \mid n \), then \( p \equiv \pm 1 \pmod{8} \). Thus, \( 3, 5 \nmid n \).
   - Every prime dividing \( n \) must follow \( p \equiv \pm 1 \pmod{12} \) and \( p \equiv \pm 1 \pmod{5} \). The first prime satisfying these conditions is \( p = 71 \), so \( n \ge 71 \).

7. **Composite \( n \)**:
   - Take the least prime factor \( q \) of \( n \). Observe that \( q < \sqrt{n} \).
   - All of \( 1, 2, \ldots, q-1 \) are quadratic residues modulo \( n \) and hence modulo \( q \). This is a contradiction because there are too many quadratic residues. Hence, we reach a contradiction.

8. **Prime \( n \)**:
   - Let \( n = a^2 + b \). Then all \( 1 \le x \le 1 + a \) are quadratic residues modulo \( n \).

9. **Contradiction**:
   - Using the results from the referenced paper, there should be much less than one set of \( a+1 \) consecutive quadratic residues, leading to a contradiction.

10. **Final Conclusion**:
    - The only values of \( n \) that satisfy the given conditions are \( \boxed{n = 1, 2, 12} \).