21
\$\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\$
4
  • 5
    \$\begingroup\$ Some existing answers are assuming that 0 <= q < n. You should probably clarify whether or not this is an acceptable assumption. \$\endgroup\$ Nov 30, 2015 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, 2015 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\$ Nov 30, 2015 at 16:17
  • \$\begingroup\$ You could give a small bonus for solutions accepting arbitrary q \$\endgroup\$
    – Bakuriu
    Dec 2, 2015 at 17:41

23 Answers 23

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\$
2
  • \$\begingroup\$ Stupid argument ordering \$\endgroup\$ Mar 26, 2016 at 15:56
  • \$\begingroup\$ What?! I never knew PowerMod could take a fractional argument! \$\endgroup\$ Jan 28, 2017 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\$
0
7
\$\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\$
2
  • \$\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\$ Dec 1, 2015 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, 2015 at 21:00
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
  • 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, 2015 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\$
0
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\$
0
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\$
7
  • \$\begingroup\$ What is the ...Array syntax? I still don't get it. \$\endgroup\$ Dec 1, 2015 at 12:40
  • \$\begingroup\$ Hope this edit is better for you. \$\endgroup\$ Dec 1, 2015 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\$ Dec 1, 2015 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, 2015 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, 2015 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\$
2
  • \$\begingroup\$ You can lose the braces and make it ->q,n{}. \$\endgroup\$
    – Vasu Adari
    Dec 3, 2015 at 8:00
  • \$\begingroup\$ @VasuAdari Cool, I did not know that. Thank you. \$\endgroup\$ Dec 3, 2015 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\$
1
  • \$\begingroup\$ This is a very interesting take on the truthy/falsey condition @user81655. Excellent work! \$\endgroup\$
    – Sherlock9
    Dec 1, 2015 at 17:37
1
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 13 chars / 25 bytes

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

Try it here (Firefox only).

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I tested your code with 15 22 and it said false. \$\endgroup\$
    – Sherlock9
    Dec 1, 2015 at 0:01
  • \$\begingroup\$ @Sherlock9 Fixed. \$\endgroup\$ Dec 1, 2015 at 3:24
  • \$\begingroup\$ No custom codepage? This is not a golfing language! \$\endgroup\$ Mar 26, 2016 at 15:58
  • \$\begingroup\$ There is now, but the code page was made long after the challenge. \$\endgroup\$ Mar 26, 2016 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\$
2
  • 1
    \$\begingroup\$ Nice! Hint: 0oV is equivalent to Vo. \$\endgroup\$ Dec 2, 2015 at 22:53
  • \$\begingroup\$ Didn't know that. Thanks! \$\endgroup\$ Dec 2, 2015 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\$
0
\$\begingroup\$

C (gcc), 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!

Does a simple for loop, brute forcing the squares.

\$\endgroup\$
0

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.