check multiple of n value as modular congruence

Question

Now i want to check that if value

int a = pow(9.0,100);
int b = 81;
int c = 547;

when i use a - b, the value should be can divide by c without remainder;

if( (a-b) % 547 == 0 )
     cout << "Correct" << endl;
else
     cout << "Wrong" << endl;

but the output always go wrong and i see website links. the answer should be correct. Link can be reference to thread here : How to calculate modulus of large numbers?

but mine one when do the congruence modulo it's involve minus sign. so dont know how to write the algorithm

It's equivalent to checking (9^100) = b mod c, and you can use the other answer. — Paul Hankin, May 29 '14 at 08:22
`(a-81)%547=0` is the same as `a%547=81` (assuming a is non-negative, which it is here). — Paul Hankin, May 29 '14 at 10:28
Duplicate of http://stackoverflow.com/q/8287144/3088138, http://stackoverflow.com/q/23846699/3088138 and likely many others. — Lutz Lehmann, May 29 '14 at 11:54

score 2 · Answer 1 · answered May 29 '14 at 08:49

2

9^100 is about 10^95, so it overflow int. Instead of calculating 10^95 and then modulo you can calucate it with normal int with something like this:

int c=1;
for(int i=0; i<100; ++i) 
    c = (c * 9) % 547;

so c value is always below 547. You can also speed it up by using binary power method.

For your second question - easiest method to compute mod value for negative value is to do this with this code:

int mod(int a, int n) {
    int res = a % n;
    if (res < 0) res = res + n;
    return res;
}

answered May 29 '14 at 08:49

Lukasz

i know how to calculate the pow and modulo already.. but my first variable have to minus the b .. and your calculation doesn't involve any minus? – user3664490 May 29 '14 at 09:26
try function from my answer: mod(a-b, 547) – Lukasz May 30 '14 at 07:45
even without the pow() function ? – user3664490 May 30 '14 at 07:51

score 1 · Answer 2 · answered May 29 '14 at 08:23

1

9^100 is likley of out range for int. So you should calculate powermod(9,100,N) where N can be int or use class that can store arbitrary size integer

answered May 29 '14 at 08:23

Luka Rahne

1

The point is that you can reduce intermediate results so that you never get numerical overflow. One has `(a*b) mod N == ((a mod N)*(b mod N)) mod N` so that there are never numbers larger than N² during the computation of powermod. – Lutz Lehmann May 29 '14 at 11:47

2 Answers2