Congruence Relations

Question

Given 3 positive integers a, b, and n (whose maximum values are the maximum representable integer value in your language), output a truthy value if a ≡ b (mod n), and falsey otherwise. For those unfamiliar with congruency relations, a ≡ b (mod n) is true iff a mod n = b mod n (or, equivalently, (a - b) mod n = 0).

Restrictions

• Built-in congruence testing methods are forbidden
• Built-in modulo operations are forbidden (this includes operations such as Python's divmod function, which return both the quotient and the remainder, as well as divisibility functions, residue system functions, and the like)

Test Cases

(1, 2, 3) -> False
(2, 4, 2) -> True
(3, 9, 10) -> False
(25, 45, 20) -> True
(4, 5, 1) -> True
(83, 73, 59) -> False
(70, 79, 29) -> False
(16, 44, 86) -> False
(28, 78, 5) -> True
(73, 31, 14) -> True
(9, 9, 88) -> True
(20, 7, 82) -> False

This is code-golf, so shortest code (in bytes) wins, with earliest submission as a tiebreaker.

Answer 1

Jelly, 5 bytes

_ÆD⁵e

Making heavy use of Anything else that is not forbidden is allowed.

Try it online!

How it works

_ÆD⁵e  Main link. Left input: a. Right input: b. Additional input: n

_      Subtract b from a.
 ÆD    Compute all divisors of the difference.
   ⁵e  Test if n is among the divisors.

Answer 2

Python 2, 27 bytes

lambda a,b,n:(a-b)/n*n==a-b

Checks if a-b is a multiple of n by dividing by n, which automatically floors, and seeing if multiplying back by n gives the same result.

Answer 3

Julia, 24 bytes

f(a,b,n,t=a-b)=t÷n==t/n

This is a function that accepts three integers and returns a boolean.

We simply test whether a - b integer divded by n is equal to a - b float divided by n. This will be true when there is no remainder from division, i.e. a - b | n, which implies that a - b (mod n) = 0.

Answer 4

Pyth, 7 bytes

!@UQ-FE

Uses Pyth's cyclic indexing.

  UQ         range(first line). [0,...,Q-1]
    -FE      Fold subtraction over the second line.
 @           Cyclic index UQ at -FE
!            Logical NOT

Answer 5

Haskell, 23 bytes

(a#b)n=div(a-b)n*n==a-b

Usage example: (28#78)5 -> True.

Same method as in @xnor's answer.

Answer 6

Minkolang 0.15, 14 11 bytes

nn-n$d:*=N.

Try it here! Input is expected as a b n.

Explanation:

n              Take number from input -> a
 n             Take number from input -> a, b
  -            Subtract               -> a-b
   n           Take number from input -> a-b, n
    $d         Duplicate stack        -> a-b, n, a-b, n
      :        Integer division       -> a-b, n, (a-b)//n
       *       Multiply               -> a-b, (a-b)//n*n
        =      1 if equal, 0 otherwise
         N.    Output as number and stop.

Answer 7

MATL, 9 bytes

Sdt:i*0hm

Input format is

[a b]
n

Try it online!

S     % implicitly input [a, b]. Sort this array
d     % compute difference. Gives abs(a-b)
t:    % duplicate and generate vector [1,2,...,abs(a-b)]; or [] if a==b
i*    % input n and multiply to obtain [n,2*n,...,abs(a-b)*n]; or []
0h    % concatenate element 0
m     % ismember function. Implicitly display

Answer 8

Retina, 20

^(1+) \1*(1*) \1*\2$

Input is given in unary, space-separated, in order n a b. Output 1 for truthy and 0 for falsey.

Try it online.

---

If you prefer decimal input then you can do this:

\d+
$&$*1
^(1+) \1*(1*) \1*\2$

Try it online.

Answer 9

APL, 15 bytes

{(⌊d)=d←⍺÷⍨-/⍵}

This is a dyadic function that accepts n on the left and a and b as an array on the right.

The approach here is basically the same as in my Julia answer. We test whether a - b / n is equal to the floor of itself, which will be true when a - b (mod n) = 0.

Answer 10

JavaScript (ES6), 27 bytes

@CᴏɴᴏʀO'Bʀɪᴇɴ posted a version which does not work; here is the "common algorithm" that people are using in a form which "works":

(a,b,n)=>n*(0|(a-b)/n)==a-b

The word "works" is in scare quotes because the shortcut we're using for Math.floor() implicitly truncates a number to be in the signed 32-bit range, so this cannot handle the full 52-bit-or-whatever space of integers that JavaScript can describe.

Answer 11

CJam, 7 bytes

l~-\,=!

Input order is n a b.

Test it here.

Explanation

l~  e# Read input and evaluate to push n, a and b onto the stack.
-   e# Subtract b from a.
\,  e# Swap with n and turn into range [0 1 ... n-1].
=   e# Get (a-b)th element from that range, which uses cyclic indexing. This is
    e# equivalent to modulo, and as opposed to the built-in % it also works correctly
    e# for negative (a-b).
!   e# Negate, because a 0 result from the previous computation means they are congruent.

Answer 12

Python 3, 27 bytes

lambda a,b,n:pow(a-b,1,n)<1

pow(x,y,n) calculates (x**y)%n, so this is just (a-b)**1%n.

Answer 13

ES6, 28 bytes

(a,b,n)=>!/\./.test((a-b)/n)

Works by looking for a decimal point in (a-b)/n which I'm hoping is allowed.

Answer 14

Seriously, 10 bytes

,,,-A│\)/=

Takes input as N\nA\nB\n (capital letters used to distinguish from newlines).

Try it online

This uses the same method as @AlexA's answer

Explanation (capital letters used as variable names for explanatory purposes):

,,,-A│\)/=
,,,         push N, A, B
   -A       push C = abs(A-B)
     │      duplicate entire stack (result is [N, C, N, C])
      \)/=  1 if C//N == C/N (floored division equals float division)

Answer 15

F#, 24 bytes

fun a b n->(a-b)/n*n=a-b

Implements the same check as @xnor's answer.