C++

Forum

 
solve congruency

hnkwana (5)
Write a procedure to solve a pair of congruences of the form

x ≡ a (mod m)
x ≡ b (mod n)

where m and n are relatively prime. The existence and uniqueness (in Z_{mn} ) of the solution to such a problem is guaranteed by the Chinese Remainder Theorem. Therefore, call your procedure crt. It should take two Mod objects as arguments and produce a Mod value in return. Your procedure should be declared like this:

Mod crt(const Mod a, const Mod b);
I managed to get the mod.h file correct and now have to fill in the rest but am stuck.please help solve the last part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
  //mod.h
#ifndef MOD_H
#define MOD_H
#include <iostream>
using namespace std;

const long INITIAL_DEFAULT_MODULUS = 2;

class Mod {
private:
  long mod;
  long val;
  static long default_modulus;
  void adjust_val() {
    val = val % mod;
    if (val < 0)
      val += mod;
  }

public:
  // initializers
  Mod() {
    mod = get_default_modulus();
    val = 0;
  }

  Mod(long x) {
    mod = get_default_modulus();
    val = x;
    adjust_val();
  }

  Mod(long x, long m) {
    if (m <= 0) {
      val = 0;
      mod = 0;
    } else {
      mod = m;
      val = x;
      adjust_val();
    }
  }

  // invalid if mod==0
  bool is_invalid() const { return mod == 0; }

  // getters and setters
  long get_val() const { return val; }

  void set_val(long x) {
    if (mod == 0)
      return; // no change for an invalid object
    val = x;
    adjust_val();
  }

  long get_mod() const { return mod; }

  void set_mod(long m) {
    if (m <= 0) {
      mod = 0;
      val = 0;
    } else {
      mod = m;
      adjust_val();
    }
  }

  static void set_default_modulus(long m) {
    if (m <= 0) {
      default_modulus = INITIAL_DEFAULT_MODULUS;
    } else {
      default_modulus = m;
    }
  }

  static long get_default_modulus() {
    if (default_modulus <= 0)
      set_default_modulus(INITIAL_DEFAULT_MODULUS);
    return default_modulus;
  }

  // comparisons
  bool operator==(const Mod &that) const {
    return ((val == that.val) && (mod == that.mod));
  }

  bool operator==(long that) const { return (*this) == Mod(that, mod); }

  bool operator!=(const Mod &that) const {
    return ((val != that.val) || (mod != that.mod));
  }

  bool operator!=(long that) const { return (*this) != Mod(that, mod); }

  bool operator<(const Mod &that) const {
    if (mod < that.mod)
      return true;
    if (mod > that.mod)
      return false;
    if (val < that.val)
      return true;
    return false;
  }

  // addition
  Mod add(Mod that) const; // only declaration, definition in Mod.cc

  Mod operator+(const Mod &x) const { return add(x); }

  Mod operator+(long x) const { return add(Mod(x, mod)); }

  Mod operator+=(const Mod &x) {
    *this = add(x);
    return *this;
  }

  Mod operator+=(long x) {
    *this = add(Mod(x, mod));
    return *this;
  }

  // substraction
  Mod operator-() const { return Mod(-val, mod); }

  Mod operator-(const Mod &x) const { return (*this) + (-x); }

  Mod operator-(long x) const { return (*this) + (-x); }

  Mod operator-=(const Mod &x) {
    *this = add(-x);
    return *this;
  }

  Mod operator-=(long x) {
    *this = *this + (-x);
    return *this;
  }

  // multiplication
  Mod multiply(Mod that) const; // only declaration, definition in Mod.cc

  Mod operator*(const Mod &x) const { return multiply(x); }

  Mod operator*(long x) const { return multiply(Mod(x, mod)); }

  Mod operator*=(const Mod &x) {
    *this = multiply(x);
    return *this;
  }

  Mod operator*=(long x) {
    *this = multiply(Mod(x, val));
    return *this;
  }

  // division
  Mod inverse() const; // only declaration, definition in Mod.cc

  Mod operator/(const Mod &x) const { return multiply(x.inverse()); }

  Mod operator/(long x) const { return multiply(Mod(x, mod).inverse()); }

  Mod operator/=(const Mod &x) {
    *this = multiply(x.inverse());
    return *this;
  }

  Mod operator/=(long x) {
    *this = multiply(Mod(x, mod).inverse());
    return *this;
  }

  // exponentiation
  Mod pow(long k) const; // only declaration, definition in Mod.cc
};

// writing to output streams
// only declaration, definition in Mod.cc
ostream &operator<<(ostream &os, const Mod &M);

// some binary operations must have the arguments switched inline
inline bool operator==(long x, const Mod &y) { return (y == x); }
inline bool operator!=(long x, const Mod &y) { return (y != x); }
inline Mod operator+(long x, Mod y) { return y + x; }
inline Mod operator-(long x, Mod y) { return (-y) + x; }
inline Mod operator*(long x, Mod y) { return y * x; }
inline Mod operator/(long x, Mod y) { return y.inverse() * x; }

#endif
//then solve the congruecy

#include "Mod.h"
long crt(long a, long m, long b, long n){
//to do
}
Mod crt(const Mod a, const Mod b){
//to do
}
int main(){
    cout <<crt(Mod(23,110), Mod(10,63))<<endl;
}
Last edited on
jonnin (11444)
but am stuck

what are you stuck on. Is it the math of the problem, or the coding of the solution?
hnkwana (5)
the coding, I do not understand how to implement the mathematics as a c++ code
Last edited on
jonnin (11444)
ok. tell us what steps you will take to solve this by hand and we can turn that into code.
Duthomhas (13214)
I suspect you have not yet taken any courses in number theory or linear algebra or the like.

The Chinese Remainder Theorem is a way of finding a number that satisfies two or more congruences.


A congruence is the relationship to a division’s remainder (not caring what the quotient is).

That is, the following two things mean the same thing:

    x ≡ r (mod d)
    x = dq + r

Where r is the remainder, d is the divisor, and q is the quotient, and all of them are non-negative integers. The three-line equal sign is read “is congruent to”. So “x is congruent to r modulo d”.

The second way of writing it is nice and algebraic.
The first way of writing it is just a convenience, and the standard notation (in the Western world) for writing it is “x = a (mod n)”. (And k is often used instead of q.)

To make sense, here is an example using concrete values.

    16 ≡ 1 (mod 5)     →     16 = 5k + 1     →     16 = 5(3) + 1


One other thing to notice is that x and a are interchangeable when written using the congruence notation. Hence, the following two are the same:

    4 ≡ 1 (mod 3)
    1 ≡ 4 (mod 3)

This is because the “(mod 3)” applies to both sides of the “≡”. Hopefully this point makes the congruence notation fairly obvious.

    1 ≡ 1 (mod 3)
    4 ≡ 1 (mod 3)
    7 ≡ 1 (mod 3)
   10 ≡ 1 (mod 3)
    etc


You are asked to solve a system of two equations.
Fortunately, there is a very simple way of thinking about this. We can look at our last example, and realize we have an arithmetic sequence.

    1 + 3 + 3 + 3 + …     →     1, 4, 7, 10, …

Using our congruence notation, that’s:

    x ≡ a (mod n)     →     a + n + n + n + …


Let us solve a simple system as an example. Given:

    x = 2 (mod 3)
    x = 3 (mod 5)

3 and 5 are coprime, so we are good to go:

    x     →     2 + 3 + …     →     2, 5, 8, 11, 14, 17, 20, 23, …
    x     →     3 + 5 + …     →     3, 8, 13, 18, 23, …

The common subsequence is:

    x     →     8, 23, …

Just choose the first element in the sequence: x = 8. That’s it!
Both of the following are true:

    8 ≡ 2 (mod 3)
    8 ≡ 3 (mod 5)



But, the modulus?
Yes, you also need to return a new modulus. Since all the modulii are coprime, just multiply them together. So:

    x = 8 (mod 15)

Final answer.

Notice something cool? The answer is less than the divisor. 8 < 15. This makes sense, right?


How to turn this into code
You need a loop that calculates the two arithmetic sequences, incrementing to the next element of whichever sequence has the smaller value. Using the example above:

    x = a (mod m)     →     a = 2, m = 3
    x = b (mod n)     →     b = 3, n = 5

Since (a < b), we’ll add m=3 to a:

    a = 5
    b = 3

Now (b < a), so we’ll add n=5 to b:

    a = 5
    b = 8

Again, (a < b), so add m=3 to a:

    a = 8
    b = 8

Finally, (a == b), and we can return a=b=8:
 
 
  return a;

Again, put it in a loop.
This finishes your long crt(long a, long m, long b, long n) function.

Next, in your Mod crt(Mod a, Mod b) function, you only need call the first crt() function with the appropriate pieces of the a and b arguments:
 
 
  long x = crt(a.val, a.mod, b.val, b.mod);

Then compose a new Mod object with the x and (a.mod*b.mod) values.

This is a very simple, brute force solution. For the numbers you are working with it will work just fine. But it is certainly possible to improve this significantly.


Error handling
It appears that your function will never be given non-coprime divisors. If that is the case, then you do not need to check. But if it is not, you should first verify that your two mod values are coprime. C++ provides the gcd() function (include <numeric>).

1
2
 
if (std::gcd( a.mod, b.mod ) != 1) 
  throw "divisors not coprime, cannot use Chinese Remainder Theorem";

I do not see a way to indicate failure in your code; hence I threw an exception. There are all kinds of other ways to indicate failure. For example, you could make your Mod object invalid by setting mod = 0.

Again, your instructions very loosely imply that the divisors are guaranteed to be coprime by the time your crt() functions get it. This is a point I would clarify with the instructor (or with any notes you have not shared with us).

Hope this helps.

I’ve got to stop making answers this pretty. I’m gonna give myself carpal tunnel syndrome…
Enoizat (1343)
That’s an awesome answer, Duthomhas, as many others I’ve read from you.
It’s very clear and informative even for me, who usually start yawning as soon as I read about math in my native language :-)
hnkwana (5)
thank you so much, I understand it now
Topic archived. No new replies allowed.