Is q a quadratic residue of n?

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 1

Pyth, 9 bytes

}Em%*ddQQ

Try it online: Demonstration or Test Suite

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 2

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 3

Par, 11 9 bytes

✶X[²x%)↔,

Each character uses just one byte; see here.

Explanation

✶              ## Read two numbers
X              ## Assign second to x
[              ## Map
 ²             ## Square
 x%            ## Mod x
)              ## 
↔              ## Swap
,              ## Count

Removed two bytes thanks to Jakube.

Answer 4

LabVIEW, 16 15 Equivalent bytes

Counted according to my meta post.

Answer 5

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 6

Haskell, 31 bytes

Saved 3 bytes thanks to Martin Büttner.

q#n=elem q[mod(x^2)n|x<-[1..n]]

Answer 7

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

Answer 8

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.

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 9

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.

Answer 10

Mathematica, 27 bytes

PowerModList[#,1/2,#2]!={}&

Usage:

In[1]:= PowerModList[#,1/2,#2]!={}&[1,5]

Out[1]= True

Answer 11

Javascript ES6, 42 bytes

(q,n)=>[...Array(n)].some((x,y)=>y*y%n==q)

Credits to @apsilers for serious bytes saved!

Answer 12

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 (permalinks are having more issues, but you can copy and paste the code into a blank page 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 13

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 14

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 15

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 16

, 13 chars / 25 bytes

⟦Ѧí]ĉ⇀_²%í≔î)

Try it here (Firefox only).

Answer 17

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 18

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!

Answer 19

Pari/GP, 25 bytes

(q,n)->issquare(Mod(q,n))

Try it online!

Answer 20

JavaScript (Node.js), 33 bytes

q=>n=>f=(t=n)=>t&&f(t-1)|t*t%n==q

Try it online!

Why no one do this

Answer 21

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 22

Milky Way 1.0.2, 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.