Solve the Congruency

I simply went through all the values of $R$ and $M$ and searched for a solution $x.$ Note that instead of building a list of solutions, I simply made a sum of solutions, because that's all the problem asks for. Also, if there are no solutions for a certain $R$ and $M,$ then the program does nothing, because it is pointless to add $0$ to a sum.

def congruenceSolutions():
    """Solves a modular congruence for a list of values (txt)"""

    solutionSum = 0

    file = open("file.txt", "r")

    for line in file:
        # The congruence is Rx == 1 (mod M)
        line = line.split()

        R = int(line[0])
        M = int(line[1])

        for x in range(M):
            if (R*x) % M == 1:
                solutionSum += x
                break

                # finds the solution x in the set {0, 1, 2, 3, ..., M-1} (if it exists) and then stops;
                # if it doesn't find one, does nothing (because then the function defaults to 0)

    return solutionSum

Rx (mod M) = 1 implies that a multiplicative inverse exists which implies that R and M must be relatively prime . Thus we can determine if there is a solution for x by Euclid's algorithm. And by using the Extended Euclid's Algorithm we can determine which x exists such that Rx + My = 1. X may or may not be negative so simply giving x % M will return the correct x. Also we know this is the smallest possible x because if it weren't, that would imply there are two numbers less than M that solve Rx (mod M) = 1 which is also impossible by the Order Theorem for coprime numbers.

Here is my code:

#This is the wrapper function that ensure the first value is always the larger one
def ExtEucAlgo(x,y):
    if (x > y): return EEASub(x,1,0,y,0,1)
    elif (x < y): return EEASub(y,1,0,x,0,1)
    else: return (x,1,0)

#The EEA algorithm
def EEASub(x,a,b,y,c,d):
    if (y == 0): return (x,a,b)
    quotient = x//y
    remainder = x%y
    NEWc = a - (c*quotient)
    NEWd = b - (d*quotient)
    return EEASub(y,c,d,remainder,NEWc, NEWd)

def brilliantSol():
    sum = 0
    f = open("brilliant.txt")
    for line in f:
        nums = line.split()
        R = int(nums[0])
        M = int(nums[1])
        #The algorithm solves A*(multgreater) + B*(multlesser) = 1 where A > B.
        (gcd, multgreater, multlesser) = ExtEucAlgo(x,y)
        if (gcd == 1):
            if (R > M):
                #R was greater so we want multgreater
                sum += (multgreater % M)
            if (R <= M):
                #R was lesser so we want multlesser
                sum += (multlesser % M)
    return sum

print(brilliantSol())

# Room for improvement :)   
# Rx mod M = 1
answers = []
with open('congruency.txt', 'r') as f:
    for line in f:
        R, M = line.split(' ')
        R = int(R)
        M = int(M)
        answer = 0
        for x in range(1, 3000):
            if R * x % M == 1:
                answer = x
                break
        answers.append(answer)
print '{0}'.format(sum(answers))[-3:]

Brute force.

Yes, I know that this is very ugly, badly organized, unreadable code. But it's a one-liner, for some definition of that phrase.

import Data.Maybe
import Data.List
main = readFile "pairs.txt" >>= (print . sum . map ((\[r, m] -> (fromMaybe 0 $ find ((== 1) . (`rem` m) . (* r)) [1..m-1])) . map read . words) . lines)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<string.h>
using namespace std;
int R,M,conta;
int main()
{   
    FILE *pf;
    pf=fopen("input.txt","r");
    for(int i=1;i<=1000;i++) {
       fscanf(pf,"%d %d",&R,&M); 
          for(int j=1;j<=M;j++) 
             if((R*j)%M==1) {conta+=j; conta=conta%1000; break;} 
    }
  fclose(pf);
  pf=fopen("output.txt","w"); fprintf(pf,"%d\n",conta); 
  fclose(pf);
    return 0;
}

conta=545

Java code:

import java.util.Scanner;
public class brilliant201408311800{
    public static void main(String args[]){
        final int n=1000;
        Scanner sc = new Scanner(System.in);
        int[] s = new int[n];
        int r,m;
        for(int i=0;i<n;i++){
            r = sc.nextInt();
            m = sc.nextInt();
            if(gcd(r,m)!=1){
                s[i] = 0;
                continue;
            }
            if(m==1){
                s[i] = 0;
                continue;
            }
            for(int x=1;;x++){
                if(r*x%m==1){
                    s[i] = x;
                    break;
                }
            }
        }
        int t = 0;
        for(int i=0;i<n;i++) t += s[i];
        System.out.println(t%1000);
    }
    private static int gcd(int a,int b){
        if(a==0) return b;
        return gcd(Math.abs(a-b),a);
    }
}

Output: 545

Here is my code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

file = open("brilliant Congruence solver.txt",'r')
strings = file.readlines()

string2 = []
for i in strings:
    string2.append(i.split())



def diophantineSolution(R, M):
    x = 0
    for i in range(M):
        if R*i % M == 1:
            x = i
    return x

total = 0

for i in string2:
    R = int(i[0])
    M = int(i[1])
    total += diophantineSolution(R,M)

Code Follows:

def extended_gcd(aa, bb):
        lastremainder, remainder = abs(aa), abs(bb)
        x, lastx, y, lasty = 0, 1, 1, 0
        while remainder:
            lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
            x, lastx = lastx - quotient*x, x
            y, lasty = lasty - quotient*y, y
        return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return 0
    return x % m

f = open('pairs.txt')
s = 0
while True:
    l = f.readline()
    if not l: break
    x = [int(i) for i in l.split(' ')]
    s += modinv(x[0]%x[1],x[1])

print s

I don't think this solution is clever but it highlights some functional techniques

#Import the numbers from the file    

SetDirectory@NotebookDirectory[];
data = Import["pairs.txt", "Data"];

#Compute Mod[R x, M] for each x between 1 and M with cong. 
#Map cong over the list of pairs and return the result 
#of the mod operation and the value of x as an ordered pair

cong = Function[{R, M}, {(R #)~Mod~M, #} & /@ Range[M]];
crunched = cong[#[[1]], #[[2]]] & /@ data;

#Find the solutions by taking every result with 1 as the first element.

success = Function[{line}, Select[line, #[[1]] == 1 &]];
results = success /@ crunched;

#Add all of the values of x together

Total[Part[#, 2] & /@ First /@ Select[results, # != {} &]]

159545

$Rx \equiv 1$ (mod $M$ ) has a solution for $x$ if and only if $1$ is divisible by the greatest common divisor of $R$ and $M$ but since 1 is only divisible by 1, we must only find numbers in the list, such that $GCD(R,M) = 1$ .

Since $GCD(R,M)$ is also the number of solutions of the congruency, then there's only one or zero solutions for each pair of numbers in the file.

If $GCD(R,M) \neq 1$ then S = 0, else we check for $x$ from 0 to $M$ if $R x - 1$ is divisible by $M$ , and that is our solution for $x$ .

I made a program in C to solve this, but I'm not sure if I should place it here too.

$R, M$ are small enough in the input that trying all $x \in \{1 \ldots, M-1\}$ to determine $S(R,M)$ is feasible. The workhorse function in this solution then is

def solution(r, m):
    for x in range(1, m):
        if r * x % m == 1:
            return x
    return 0

Sum the output of this function over every line of the input to get the solution.

If such an $x$ exists, it must be less than $M$ . For each pair of integers $(R,M)$ , we can loop over each integer from 1 through M, and if $Rx\equiv 1\pmod M$ (use '%' in Python), then we can append $x$ to L (it is not necessary to append 0s since they don't affect the sum). The answer is simply the sum of the elements in L .

def S(r, m):
    x = 0
    while True:
        if x == m + 1:
            break
        if (r * x) % m == 1 % m:
            return x
            break
        x += 1
    return 0

file = open("Congruency.txt")
def looper(f):
    list_of_results = []
    total_lines = 0
    for line in f:
        total_lines += 1
        r = ""
        m = ""
        for i in range(len(line)):
            if line[i] != " ":
                r += line[i]
            else:
                m += line[i + 1::]
                break
        r = int(r)
        m = int(m)
        list_of_results.append(S(r,m))
    print total_lines
    return list_of_results
def sumer(li):
    total = 0
    for n in li:
        total += n
    return total

print sumer(looper(file))

O(M) brute force, checking all possible values of S(R,M), works.

C++

#include <iostream>
using namespace std;

int main(){
    int N = 1000, res = 0, a, b;
    for(int i = 0; i<1000; i++){
        cin >> a >> b;
        for(int j = 0; j<b; j++) if(a*j%b==1) res+=j;
    }
    cout << res%1000 << '\n';
}

(There also exists an O(log(M)^2) solution using Euclidean algorithm.)

# Great Common Divisor - Euclid's Algorithm
def gcd(a,b):
    if a < b:
        a, b = b, a
    while b != 0:
        a, b = b, a % b
    return a



f = open('pairs.txt','r')
li=[]
for val in f.read().split():
    li.append(int(val))
f.close()

sum=0
for j in range(len(li)/2):
    a=li[2*j]
    b=li[2*j+1]
    if gcd(a,b)==1:
        for i in range(b):
             if (a*i)%b == 1:
                sum += i
                break

print sum

For small values of $M$ (such as the ones provided in the input file) pure brute force is enough to determine $S(R,M)$ : the only thing we need is to realize that it is sufficient to check all $x$ such that $1\leq x < M$ :

def inv(r,m):
    for i in range(1,m):
        if i*r%m==1: return i
    return 0

And then we just walk over the list of pairs and sum up the values:

T = 0
for line in open('con.txt').readlines():
    r, m = [ int(x) for x in line.split() ]
    T += inv(r,m)

The integer $x$ is also known as the modular multiplicative inverse of $R$ modulo $M$ .

First, let us prove that it exists if and only if $R$ and $M$ are coprime.

By Bézout's identity, there exist integers $x$ and $y$ such that $Rx + My = gcd(R,M)$

and $gcd(R,M)$ is the smallest positive integer that can be written that way. Modulo $M$ , this becomes

$Rx = gcd(R,M) \pmod M$

and since $gcd(R,M)$ is the smallest positive integer that can be written in that form, it must be $1$ .

By using the Extended Euclidean Algorithm, we can easily compute the smallest integers $x$ and $y$ that satisfy these requirements in logarithmic time, and we simply iterate through the list of pairs, computing $x$ or ignoring the line if $R$ and $M$ aren't coprime.