[Question]
  [
Given two inputs `q n` determine if `q` is a quadratic residue of `n`.
That is, is there an `x` where `x**2 == q (mod n)` or is `q` a square mod `n`?
**Input**
Two integers `q` and `n`, where `q` and `n` are any integers `0 <= q < n`.
**Output**
A truthy or a falsey.
Optionally, print any (or all) `x` that is `x**2 == q (mod n)`
**Examples**
```
>>> quadratic_residue(1, 5)
True
>>> quadratic_residue(3, 8)
False
>>> quadratic_residue(15, 22)
True
```
**Rules**
Your code must be a program or a function. The inputs can be in any order. This is code golf, so **shortest code in bytes wins.**
If anything is unclear or otherwise needs fixing, please let me know.
**Bonuses**
* 2-byte bonus if your function accepts `q` as any arbitrary integer.
## Catalogue
```
var QUESTION_ID=65329;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}
```
```
body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```
```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>
```
  
[Answer]
## Mathematica, 25 bytes
```
AtomQ@PowerMod[#,1/2,#2]&
```
Mathematica, being Mathematica, naturally has a builtin for calculating modulo nth roots, via `PowerMod`. If a solution exists the smallest feasible solution is returned, otherwise the original expression (plus a message).
To get an actual truthy/falsy output we pass the result to `AtomQ`, which checks whether an expression can be broken down. Integers are atomic, returning `True`, whilst the non-atomic `PowerMod[q,1/2,n]` returns `False`
Thanks to @MartinB√ºttner for golf tips and function hunting with me.
[Answer]
# [Par](http://ypnypn.github.io/Par/), ~~11~~ 9 bytes
```
‚ú∂X[¬≤x%)‚Üî,
```
Each character uses just one byte; see [here](https://github.com/Ypnypn/Par/blob/gh-pages/README.md#the-encoding).
## Explanation
```
‚ú∂              ## Read two numbers
X              ## Assign second to x
[              ## Map
 ¬≤             ## Square
 x%            ## Mod x
)              ## 
‚Üî              ## Swap
,              ## Count
```
Removed two bytes thanks to Jakube.
[Answer]
# Pyth, 9 bytes
```
}Em%*ddQQ
```
Try it online: [Demonstration](http://pyth.herokuapp.com/?test_suite_input=5%0A1%0A8%0A3%0A22%0A15&input_size=2&test_suite=0&code=%7DEm%25%2AddQQ&input=5%0A1) or [Test Suite](http://pyth.herokuapp.com/?test_suite_input=5%0A1%0A8%0A3%0A22%0A15&input_size=2&test_suite=1&code=%7DEm%25%2AddQQ&input=5%0A1)
### Explanation:
```
}Em%*ddQQ   implicit: Q = first input number
  m     Q   map all numbers d of [0, 1, ..., Q-1] to:
    *dd       d*d
   %   Q      mod Q
            this gives the list of all quadratic residues
 E          read another input number
}           check, if it appears in the list of quadratic residues
```
[Answer]
# LabVIEW, ~~16~~ 15 [Equivalent bytes](http://meta.codegolf.stackexchange.com/a/7589/39490)
Counted according to my [meta post](http://meta.codegolf.stackexchange.com/a/7589/39490).
[![old](https://i.stack.imgur.com/yAIVn.jpg)](https://i.stack.imgur.com/yAIVn.jpg)
[![new](https://i.stack.imgur.com/l8KKv.jpg)](https://i.stack.imgur.com/l8KKv.jpg)
[Answer]
# Haskell, 31 bytes
Saved 3 bytes thanks to Martin B√ºttner.
```
q#n=elem q[mod(x^2)n|x<-[1..n]]
```
[Answer]
# Matlab, 29
This function squares all numbers from 0 to n and checks whether a square minus q is zero mod n.
```
@(q,n)any(~mod((0:n).^2-q,n))
```
[Answer]
# Prolog (SWI), 34 bytes
**Code:**
```
Q*N:-between(0,N,X),X*X mod N=:=Q.
```
**Explanation:**  
Checks if any square between **0** and **N** leaves **Q** when divided by **N**.
**Example:**
```
3*8.
false
15*22.
true
```
Try it online [here](http://swish.swi-prolog.org/p/fQGBdXGu.pl)
[Answer]
## CJam, 11 bytes
```
{_,2f#\f%&}
```
This unnamed block expects `q n` on the stack and leaves `[q]` on the stack as a truthy value or `""` as a falsy value.
[Test it here.](http://cjam.aditsu.net/#code=q~%0A%7B_%2C2f%23%5Cf%25%26%7D%0A~p&input=15%2022)
Credits to Sp3000 who also came up with this solution but "couldn't be bothered posting".
### Explanation
```
_,  e# Duplicate n and turn into range [0 1 ... n-1]
2f# e# Square each element in the range.
\f% e# Take each element in the range modulo n.
&   e# Set intersection with q to check if any square yields q (mod n).
```
[Answer]
# J, 9 bytes
```
e.]|i.^2:
```
Usage:
```
   1 (e.]|i.^2:) 5
1
   3 (e.]|i.^2:) 8
0
   15 (e.]|i.^2:) 22
1
```
Explanation:
```
e.]|i.^2:
    i.    [0..N-1]
      ^   to the power of
       2: 2 (constant 2 function)
  ]|      mod N       
e.        contains Q? (0/1 result)
```
Some J mechanics trivia:
Functions are grouped by 3 iteratively from the right and if there is one left, as in our case (`e. (] | (i. ^ 2:))`), the grouped part is called with the right argument (`N`) and the left out function (`e.`, "contains") called with the original left argument (`Q`) and the result of the grouped part.
(`e.]|i.*i.` and `e.]|2^~i.` also solves the problem with the same length.)
[Try it online here.](http://tryj.tk/)
[Answer]
# Mathematica, 27 bytes
```
PowerModList[#,1/2,#2]!={}&
```
Usage:
```
In[1]:= PowerModList[#,1/2,#2]!={}&[1,5]
Out[1]= True
```
[Answer]
# Javascript ES6, 42 bytes
```
(q,n)=>[...Array(n)].some((x,y)=>y*y%n==q)
```
Credits to @apsilers for serious bytes saved!
[Answer]
## [Seriously](https://github.com/Mego/Seriously), 20 bytes
```
,;R@,;‚ïó@%‚ïù`¬™‚ïú@%‚ïõ=`MŒ£
```
Takes input on two lines: `q`, then `n`. Outputs a `0` if `q` is not a quadratic residue of `n`, else a positive number representing how many `x` in `[1, q]` (inclusive) satisfy `x^2 = q (mod n)`.
[Try it online](http://seriouslylang.herokuapp.com/link/code=2c3b52402c3bbb4025bc60a6bd4025be3d604de4&input=) (permalinks are having more issues, but you can copy and paste the code into a [blank page](http://seriouslylang.herokuapp.com) in the meantime)
Explanation:
```
,;R      get q input, duplicate, push range(1, q+1)
@,;‚ïó     move the list to the back of the stack, get n input, dupe, save in reg 0
@%‚ïù      calculate q mod n and save to reg 1
`¬™‚ïú@%‚ïõ=` push this function:
  ¬™‚ïú@%     square top of stack, push reg 0 value (n), swap, and mod
  ‚ïõ=       push reg 1 value (q mod n), compare equality (1 if equal else 0)
MŒ£       map the function across the range, add results
```
[Answer]
# Python 3, ~~41~~ 40 bytes
Takes `q` and `n` and determines if `q` is in a list of squares from `0` squared to `n-1` squared.
```
lambda q,n:q in[i*i%n for i in range(n)]
```
[Answer]
# Ruby, 33 31 bytes
Saved two bytes thanks to Vasu Adari.
```
->q,n{(1..n).any?{|e|e*e%n==q}}
```
As usual Ruby's not going to beat any of the golfing languages, but it makes a good showing here.
[Answer]
# Julia, 30 bytes
```
f(q,n)=q‚àà[i^2%n for i=0:n-1]
```
This is a function `f` that accepts two integers and returns a boolean.
Ungolfed:
```
function f(q::Integer, n::Integer)
    # Generate an array of quadratic residues
    x = [i^2 % n for i = 0:n-1]
    # Determine whether q is one of these values
    return q ‚àà x
end
```
[Answer]
# JavaScript (ES6), 43 bytes
```
(q,n)=>eval('for(x=n,r=0;x--;)r+=x*x%n==q')
```
## Explanation
```
(q,n)=>
  eval(`              // eval allows us to use a for loop without {} or return
    for(x=n,r=0;x--;) // iterate over all possible values of x
      r+=x*x%n==q     // r = the number of matching x values
  `)                  // implicit: return r
```
## Test
```
q = <input type="number" id="Q" /><br />
n = <input type="number" id="N" /><br />
<button onclick="result.innerHTML=(
(q,n)=>eval('for(x=n,r=0;x--;)r+=x*x%n==q')
)(+Q.value,+N.value)">Go</button><pre id="result"></pre>
```
[Answer]
# ùîºùïäùïÑùïöùïü, 13 chars / 25 bytes
```
‚ü¶—¶√≠]ƒâ‚áÄ_¬≤%√≠‚âî√Æ)
```
`[Try it here (Firefox only).](http://molarmanful.github.io/ESMin/interpreter.html?eval=true&input=%5B3%2C8%5D&code=%E2%9F%A6%D1%A6%C3%AD%5D%C4%89%E2%87%80_%C2%B2%25%C3%AD%E2%89%94%C3%AE%29)`
[Answer]
# Japt, 10 bytes
```
Vo d_¬≤%V¬•U
```
My first official Japt golf ever! Thanks to @ETHProductions for saving a byte!
# Ungolfed / Explanation
```
Vo d_  ¬≤  %V¬• U
Vo dZ{Zp2 %V==U}  // implicit: U,V = inputs
Vo                // Create a range from 0 to n-1
   dZ{         }  // Check if any element Z in the range satisfies the condition:
       Zp2        // Is Z squared...
           %V     // modulo n...
             ==U  // equal to q?
                  // implicit output
```
[Try it online!](http://ethproductions.github.io/japt?v=master&code=MG9WIGRfsiVWpVU=&input=MTUgMjI=)
[Answer]
# C# 6 (.Net Framework 4.6) in LinqPad, 60 Bytes
```
bool b(int q,int n)=>Enumerable.Range(1,n).Any(y=>y*y%n==q);
```
[Answer]
# [Milky Way 1.0.2](https://github.com/zachgates7/Milky-Way), 41 bytes
```
:>&{~1-:2h<:>n>;:>;<<b?{_a0_^}~;?{_0_1}}!
```
This expects `q` and `n` to be solely on the stack. It outputs a `1` or `0` for the truth and false values, respectively.
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 25 bytes
```
(q,n)->issquare(Mod(q,n))
```
[Try it online!](https://tio.run/##HYg5CoAwEEWv8rHKwKRQEWz0Bp5AUgQ3AkHHqBBPH5fqLWKD04ukGQ2S2nkl3brj2C8bJtVt478oWRF/qwjdQoJbz1ezLzIM1ns1MyIRo@9zRmVeKRn1x7xiFIUxlB4 "Pari/GP ‚Äì Try It Online")
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 33 bytes
```
q=>n=>f=(t=n)=>t&&f(t-1)|t*t%n==q
```
[Try it online!](https://tio.run/##y0osSyxOLsosKNHNy09J/e9m@7/Q1i7P1i7NVqPENk/T1q5ETS1No0TXULOmRKtENc/WtvC/NVdyfl5xfk6qXk5@uoabhqGmhqmmhqYmurixpoYFNnFDoGojI7DMfwA "JavaScript (Node.js) ‚Äì Try It Online")
Why no one do this
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~49~~ 48 bytes
*-1 byte thanks to ceilingcat*
```
f(q,n,i,a){for(i=n;i--;)a=i*i%n==q?:a;return a;}
```
[Try it online!](https://tio.run/##dclBCsIwEEDRfU4xVAqJTIRWCmKMXsRNSBod0KmN6ar07LHu9S//8/rmfSlRjshI6NQchyTJsiGtjXKWtlSztePl6Ezq85QYnFnKhtg/ptDD6Z0DDbv7WQjiDE9HLBXMAtZeaV1RVnW4coUQZYPQKWV@4x7h8BebDqFtv7yUDw "C (gcc) ‚Äì Try It Online")
Does a simple for loop, brute forcing the squares.
]