22
\$\begingroup\$

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>

\$\endgroup\$
  • 5
    \$\begingroup\$ Some existing answers are assuming that 0 <= q < n. You should probably clarify whether or not this is an acceptable assumption. \$\endgroup\$ – Peter Taylor Nov 30 '15 at 14:52
  • 1
    \$\begingroup\$ I would have liked q and n to be any two integers, but so I don't break existing answers, 0 <= q < n \$\endgroup\$ – Sherlock9 Nov 30 '15 at 15:23
  • 2
    \$\begingroup\$ In this case I would have considered it reasonable to "break" the existing answers on the grounds that they weren't following the existing spec and you were just clarifying that it meant what it said rather than changing it, but it's too late now. \$\endgroup\$ – Peter Taylor Nov 30 '15 at 16:17
  • \$\begingroup\$ You could give a small bonus for solutions accepting arbitrary q \$\endgroup\$ – Bakuriu Dec 2 '15 at 17:41

22 Answers 22

6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I tried putting 7 9 as inputs, and it said "False", despite the fact that 7 is equivalent to 5^2 mod 9. \$\endgroup\$ – Nick Matteo Dec 1 '15 at 20:57
  • \$\begingroup\$ @kundor I read the integers in the reversed order. First n and than q. So try 9\n7 as input. \$\endgroup\$ – Jakube Dec 1 '15 at 21:00
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Stupid argument ordering \$\endgroup\$ – CalculatorFeline Mar 26 '16 at 15:56
  • \$\begingroup\$ What?! I never knew PowerMod could take a fractional argument! \$\endgroup\$ – Greg Martin Jan 28 '17 at 2:24
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

LabVIEW, 16 15 Equivalent bytes

Counted according to my meta post.

old

new

\$\endgroup\$
5
\$\begingroup\$

Haskell, 31 bytes

Saved 3 bytes thanks to Martin Büttner.

q#n=elem q[mod(x^2)n|x<-[1..n]]
\$\endgroup\$
  • 1
    \$\begingroup\$ Also 31 bytes: q#n=any(\x->mod(x*x)n==q)[0..n] and for 30 byte: q#n=[x|x<-[0..n],mod(x*x)n==q] which returns the list of x / empty list instead of True / False. \$\endgroup\$ – nimi Nov 30 '15 at 16:32
5
\$\begingroup\$

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))
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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).
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 27 bytes

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

Usage:

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

Out[1]= True
\$\endgroup\$
3
\$\begingroup\$

Javascript ES6, 42 bytes

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

Credits to @apsilers for serious bytes saved!

\$\endgroup\$
  • \$\begingroup\$ What is the ...Array syntax? I still don't get it. \$\endgroup\$ – Tomáš Zato Dec 1 '15 at 12:40
  • \$\begingroup\$ Hope this edit is better for you. \$\endgroup\$ – Mama Fun Roll Dec 1 '15 at 14:47
  • \$\begingroup\$ [...Array(5)] produces array of undefined, same as Array(5) alone. I am totally confused, because removing the weird syntax and using just Array(5) breaks the code. Is there any documentation for this? my console screenshot \$\endgroup\$ – Tomáš Zato Dec 1 '15 at 14:57
  • 1
    \$\begingroup\$ @TomášZato Array(5) is an array with no own-properties except length. The array-spread [...x] fills in missing numerical properties up to length. The map function can only operate on extant properties, which Array(5) alone doesn't have. For example, try Array(5).hasOwnProperty(0) (false) versus [...Array(5)].hasOwnProperty(0) (true). \$\endgroup\$ – apsillers Dec 1 '15 at 21:07
  • 1
    \$\begingroup\$ Also, using some is shorter and (I think) equivalent: (q,n)=>[...Array(n)].some((x,y)=>y*y%n==q) \$\endgroup\$ – apsillers Dec 1 '15 at 21:22
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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)]
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can lose the braces and make it ->q,n{}. \$\endgroup\$ – Vasu Adari Dec 3 '15 at 8:00
  • \$\begingroup\$ @VasuAdari Cool, I did not know that. Thank you. \$\endgroup\$ – Reinstate Monica iamnotmaynard Dec 3 '15 at 16:11
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ This is a very interesting take on the truthy/falsey condition @user81655. Excellent work! \$\endgroup\$ – Sherlock9 Dec 1 '15 at 17:37
1
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 13 chars / 25 bytes

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

Try it here (Firefox only).

\$\endgroup\$
  • 1
    \$\begingroup\$ I tested your code with 15 22 and it said false. \$\endgroup\$ – Sherlock9 Dec 1 '15 at 0:01
  • \$\begingroup\$ @Sherlock9 Fixed. \$\endgroup\$ – Mama Fun Roll Dec 1 '15 at 3:24
  • \$\begingroup\$ No custom codepage? This is not a golfing language! \$\endgroup\$ – CalculatorFeline Mar 26 '16 at 15:58
  • \$\begingroup\$ There is now, but the code page was made long after the challenge. \$\endgroup\$ – Mama Fun Roll Mar 26 '16 at 18:48
1
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice! Hint: 0oV is equivalent to Vo. \$\endgroup\$ – ETHproductions Dec 2 '15 at 22:53
  • \$\begingroup\$ Didn't know that. Thanks! \$\endgroup\$ – Mama Fun Roll Dec 2 '15 at 23:14
0
\$\begingroup\$

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);
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 25 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.