26
\$\begingroup\$

Fermat's Last Theorem, mod n

It is a well known fact that for all integers \$p>2\$, there exist no integers \$x, y, z>0\$ such that \$x^p+y^p=z^p\$. However, this statement is not true in general if we consider the integers modulo \$n\$.

You will be given \$n\$ and \$p\$, which are two positive integers with \$n>1\$. Your task will be to write a function or program to compute all positive integers \$x, y, z<n\$ such that \$(x^p+y^p)\$ and \$z^p\$ give the same remainder when divided by \$n\$.

Input

Any reasonable method of input is allowed. E.g. two separate user inputs, ordered pair, two function parameters, etc.

Output

Any reasonable method of output is valid, it may be produced by a function or output to the screen. The order the triples are listed does not matter. Triples such as (1, 2, 3) and (2, 1, 3) are considered distinct, and all distinct triples should be listed exactly once. No invalid/trivial triples such as (0, 0, 0) should be output.

The numbers \$x, y, z\$ may have any ordering within each of the triples, but that order should be consistent. For example if \$2^p+2^p\$ and \$3^p\$ have the same remainder when divided by \$n\$, you may list this triple as (2, 2, 3) or (3, 2, 2).

Examples

n p -> Possible Output
----------------------------------------------------------------
2 3 -> []
3 3 -> [(1,1,2),(2,2,1)]
3 4 -> []
4 3 -> [(1,2,1),(1,3,2),(2,1,1),(2,2,2),(2,3,3),(3,1,2),(3,2,3)]

Scoring

Shortest code in bytes with no standard loopholes wins.

\$\endgroup\$
  • \$\begingroup\$ I guess we have to specify how triplets are ordered and be consistent.. E.g. All (x,y,z) or all (z,x,y) and so on \$\endgroup\$ – AZTECCO Nov 4 at 17:06
  • \$\begingroup\$ @AZTECCO Good point, I will add that specification. \$\endgroup\$ – 79037662 Nov 4 at 17:08
  • 1
    \$\begingroup\$ I'm not convinced that solutions with z=0 are trivial. \$\endgroup\$ – Neil Nov 4 at 21:22
  • 1
    \$\begingroup\$ @Neil I didn't say they were, but they are invalid for the purposes of this question. \$\endgroup\$ – 79037662 Nov 4 at 21:37
  • 1
    \$\begingroup\$ @RosLuP Correct. \$\endgroup\$ – 79037662 Nov 8 at 14:35

17 Answers 17

7
\$\begingroup\$

Julia 1.0, 62 bytes

f(n,p,q=1:n-1)=[(x,y,z) for x=q,y=q,z=q if (x^p+y^p)%n==z^p%n]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You can drop the space after if to save a byte. \$\endgroup\$ – Glen O Nov 8 at 1:21
7
\$\begingroup\$

05AB1E, 15 10 bytes

-2 bytes by Kevin Cruijssen
-3 bytes by Grimmy

<L3ãʒImƹÖ

Try it online!

Returns a triples in the format [z,y,x].

Explanation:

<L                | Push the interval [1,n)
  3ã              | Push the triple cartesian product [1,n) x [1,n) x [1,n)
                  | E.g. with n = 3, the list begins as follows:
                  | [[1, 1, 2], [1, 2, 1], [2, 1, 3], ...]
    ʒ             | Filter the list:
     Im           | Take the p-th power of each input
                  | E.g. [1, 1, 2] --> [1^p, 1^p, 2^p]
       Æ          | Reduce by subtraction
                  | E.g. [1^p, 1^p, 2^p] -->  1^p - 1^p - 2^p
        ¹Ö        | Check if 1^p - 1^p - 2^p = 0 (mod n), and filter out if not.
\$\endgroup\$
  • 1
    \$\begingroup\$ The specification says the order of the numbers in the triple does not matter (as long as it's consistent). Is the í necessary? \$\endgroup\$ – 79037662 Nov 4 at 18:38
  • \$\begingroup\$ Ops! Yes, then it is not needed. Good catch, thanks. \$\endgroup\$ – Wisław Nov 4 at 18:43
  • 1
    \$\begingroup\$ 0Q can be _ to save a byte. \$\endgroup\$ – Kevin Cruijssen Nov 5 at 12:37
  • 2
    \$\begingroup\$ 13 bytes by outputting as triplets in the order [z,y,x]. \$\endgroup\$ – Kevin Cruijssen Nov 5 at 12:46
  • 2
    \$\begingroup\$ 10 bytes \$\endgroup\$ – Grimmy Nov 5 at 15:50
6
\$\begingroup\$

APL (Dyalog Unicode), 19 bytes

{⍸0=⍵|-/¨⍺*⍨⍳3⍴⍵-1}

The triples are returned in the format x z y. Try it online!

Explanation

{⍸0=⍵|-/¨⍺*⍨⍳3⍴⍵-1} ⍝ n is our right argument, ⍵, and p is our left, ⍺.

             3⍴⍵-1  ⍝ First, we get a triple of (n-1, n-1, n-1).
            ⍳       ⍝ Then we get the Cartesian product of three range[1, n-1).
                    ⍝ As you will see, this gives a list of (x z y) triples.
         ⍺*⍨        ⍝ We take each element of each triple to the power of p.
      -/¨           ⍝ Here we subtract over each triple, using (element - rest)
                    ⍝ This gives us (x^p - (z^p - y^p)) = x^p + y^p - z^p.
    0=              ⍝ Then we check which (x^p + y^p - z^p) equals 0.
   ⍸                ⍝ And use these results, a Boolean array,
                    ⍝ to find get the indices of the correct triples,
                    ⍝ which are our (x z y)s.
\$\endgroup\$
5
\$\begingroup\$

Jelly, 13 bytes

*ŒH§%³E
Ṗṗ3çƇ

A full program accepting command line arguments n p which prints a list representation of the results (Do note that the empty list is represented as no output).

Try it online!

How?

*ŒH§%³E - Link 1: evaluate a triple: [x, y, z], p
*       - exponentiate               [x^p, y^p, z^p]
 ŒH     - split into halves          [[x^p, y^p], [z^p]]
   §    - sums                       [x^p+y^p, z^p]
     ³  - program's 1st argument     n
    %   - modulo                     [(x^p+y^p)%n, (z^p)%n]
      E - all equal?                 (x^p+y^p)%n == (z^p)%n

Ṗṗ3çƇ - Main Link: n, p
Ṗ     - pop (implicit range of n)    [1,2,3,...,n-1]
  3   - literal three                3
 ṗ    - Cartesian power              [[1,1,1],[1,1,2],...,[n-1,n-1,n-1]]
    Ƈ - filter keep those for which:
   ç  -   last Link (1) as a dyad    Link 1([[1,1,1],[1,1,2],...,[n-1,n-1,n-1]], p)
      - implicit print
\$\endgroup\$
4
\$\begingroup\$

GAP, 63 bytes

Filtered(Tuples([1..n-1],3),i->(i[1]^p+i[2]^p-i[3]^p) mod n=0);

For example:

gap> n:=4; p:=3;
4
3
gap> Filtered(Tuples([1..n-1],3),i->(i[1]^p+i[2]^p-i[3]^p) mod n=0);
[ [ 1, 2, 1 ], [ 1, 3, 2 ], [ 2, 1, 1 ], [ 2, 2, 2 ], [ 2, 3, 3 ], 
  [ 3, 1, 2 ], [ 3, 2, 3 ] ]
\$\endgroup\$
3
\$\begingroup\$

Octave, 74 72 bytes

2 bytes saved thanks to @79037662

@(n,p){[c,b,a]=ndgrid(1:n-1) [a(k=~mod(a.^p+b.^p-c.^p,n)) b(k) c(k)]}{2}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Do you need the extra pair of parentheses in a((k=~mod(a.^p+b.^p-c.^p,n)))? \$\endgroup\$ – 79037662 Nov 4 at 17:14
  • \$\begingroup\$ @79037662 No, they are not needed. They were a leftover from some (unsuccessful) tests to try to get rid of the cell array. Thanks! \$\endgroup\$ – Luis Mendo Nov 4 at 17:22
3
\$\begingroup\$

JavaScript (ES7), 104 bytes

Takes input as (n)(p).

n=>p=>[...Array(n**3)].map((_,i)=>[i/n/n|0,i/n%n|0,i%n]).filter(([x,y,z])=>x*y*z&&(x**p+y**p)%n==z**p%n)

Try it online!

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

R, 67 bytes

function(n,p,m=t(expand.grid(a<-2:n-1,a,a)))m[,!c(1,1,-1)%*%m^p%%n]

Try it online!

expand.grid creates all possible triplets of numbers. Annoyingly, the output of expand.grid is a data frame and not a matrix, so I transpose it to coerce to a matrix m. Take the matrix product of [1,1,-1] with m^p to get \$x^p+y^p-z^p\$, then keep only the rows for which we get \$ 0 \mod n\$.

\$\endgroup\$
  • 1
    \$\begingroup\$ nice, I tried a different approach and only got down to 68 \$\endgroup\$ – MickyT Nov 4 at 17:58
  • \$\begingroup\$ @MickyT Nice idea using which with 3d indices! Here is a 65 byte version of yours, which you should post separately as it is substantially different. \$\endgroup\$ – Robin Ryder Nov 4 at 19:18
3
\$\begingroup\$

R, 65 bytes

3 btye's saved from my original idea by @robin-ryder by using subtraction, applying modulo the result.

function(n,p,q=(2:n-1)^p)which(!outer(outer(q,q,'+'),q,'-')%%n,T)

Try it online!

Makes use of outer to build a 3d array of the addition, then the subtraction. If the remainder of n is 0 output the array indices using which.

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

Wolfram Language (Mathematica), 54 bytes

n_~f~p_:=Select[Range[n-1]~Tuples~3,n|{1,1,-1}.#^p&]

Named function taking the two inputs, like f[4,3]. The | symbol typed above needs to be replaced by the 3-byte character representing the "divides" relation; \[Divides] works as well, and is used in the TIO example.

Works by testing every possible triple {x,y,z}. The only detail of note is that the dot product {1,1,-1}.#^p&, when applied to {x,y,z}, calculates x^p+y^p-z^p.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 67 66 bytes

->n,p{w=*1...n;w.product(w,w).select{|a,b,c|(a**p+b**p-c**p)%n<1}}

Try it online!

Thanks Chas Brown for -1 byte.

\$\endgroup\$
  • 2
    \$\begingroup\$ Save a byte with (a**p+b**p-c**p)%n<1 \$\endgroup\$ – Chas Brown Nov 5 at 21:29
  • \$\begingroup\$ I never knew you could pass multiple arrays to product! Very nice. \$\endgroup\$ – IMP1 Nov 6 at 10:09
1
\$\begingroup\$

Python 2, 94 bytes

n,p=input()
R=range(1,n)
print[(x,y,z)for x in R for y in R for z in R if(x**p+y**p-z**p)%n<1]

Try it online!

Pretty basic.

\$\endgroup\$
1
\$\begingroup\$

Icon, 95 bytes

procedure f(n,p)
x:=1to(t:=n-1)&y:=1to t&z:=1to t&(x^p+y^p-z^p)%n=0&write(x," ",y," ",z)&\q
end

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 13 bytes

*+_ƭ/³ḍ
Ṗṗ3çƇ

Try it online!

-2 bytes thanks to caird coinheringaahing
-1 byte borrowing a clever trick from Jonathan Allan

Explanation

*+_ƭ/³ḍ  Helper Link - given (x, y, z), determine if x^p + y^p = z^p (mod n)
*        (x^p, y^p, z^p)
    /    Reduce over
 +_ƭ     Tied operator: cycle between + and - (x^p + y^p - z^p)
     ³ḍ  Divisibility check by n (if x^p + y^p - z^p is divisible by n then x^p + y^p is congruent to z^p mod n)
Ṗṗ3çƇ    Main Link
Ṗ        Pop (remove last element) - on an integer, implicit range (1 to n-1)
 ṗ3      Cartesian power ^ 3
   çƇ    Filter: keep triples that are valid by the helper link
\$\endgroup\$
1
\$\begingroup\$

APL(NARS), chars 129, bytes 258

r←f w;n;p;a;v;i;j;b
(n p)←w⋄a←n∣p*⍨v←⍳n-1⋄r←⍬
:for i :in v⋄:for j :in v
:if a∊⍨b←n∣a[i]+a[j]⋄r←r,⊂i,j,a⍳b⋄:endif
:endfor⋄:endfor

test:

  ⎕fmt f 2 3
┌0─┐
│ 0│
└~─┘
  ⎕fmt f 3 3
┌2────────────────┐
│┌3─────┐ ┌3─────┐│
││ 1 1 2│ │ 2 2 1││
│└~─────┘ └~─────┘2
└∊────────────────┘
  ⎕fmt f 3 4
┌0─┐
│ 0│
└~─┘
  ⎕fmt f 4 3
┌7─────────────────────────────────────────────────────────────┐
│┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐│
││ 1 2 1│ │ 1 3 2│ │ 2 1 1│ │ 2 2 2│ │ 2 3 3│ │ 3 1 2│ │ 3 2 3││
│└~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘2
└∊─────────────────────────────────────────────────────────────┘
\$\endgroup\$
1
\$\begingroup\$

K (oK), 30 23 bytes

-7 bytes thanks to ngn!

{(~x!-/*/y#)#+1+!3#x-1}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ (*/y#)'' -> */y#, \$\endgroup\$ – ngn Nov 10 at 9:28
  • \$\begingroup\$ using func#list as "filter": {(~x!-/*/y#)#+1+!3#x-1} \$\endgroup\$ – ngn Nov 10 at 9:32
  • \$\begingroup\$ @ngn Filter, of course! Thanks! \$\endgroup\$ – Galen Ivanov Nov 10 at 9:36
0
\$\begingroup\$

Zsh, 90 bytes

l=({1..$[$1-1]}\ )
for x y z (${=${:-$^l$^l$^l}})(((x**$2+y**$2-z**$2)%$1))||<<<"$x $y $z"

Try it online!

Creates the list l=('1 ' '2 ' '3 ' ... '(n-1) ' ), then ${=${:-$^l$^l$^l} gets the Cartesian product and splits on spaces.

\$\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.