So , from what i have read on the internet , modulo can do this:
(a*b) % n = (a % n * b % n)%n;
Which i understand because a%n * b%n can be bigger than n , so we have to take modulo n again.But i don't get n! mod p.Algorithm from internet:
int result = 1;
for (int i = 1 ; i <= n ; i++)
{
result = (result * i ) % p;
}
cout<<result;
Let's say n = 3 , and p is 7.
When i = 1 , result = 1 % 7 ,
when i = 2 , result = (1%7 * 2) % 7 , and when i = 3 ,
result =((1%7*2) % 7 * 3) % 7.
I don't really see the connection between my first statement and this result.From what i see , for n = 2 , n! % 7 should be (1 % 7 * 2 % 7 ) % 7 , not as the algorithm would do it:(1 % 7 * 2 ) % 7.
I know the algorithm is right and i am missing something...Can anyone help me?
(a*b) % n == (a%n * b) % nis also true.ais representable asq*n + rwhereq=floor(a/n)andr=a%n. Thena*b == (q*n+r)*b == n*q*b + r*b. The first component is clearly divisible byn, so(a*b)%n == (r*b)%n == (a%n * b) %n. QEDa=x mod nandb=y mod nthena*b = x*y mod n. So ifa%n = x%nandb%n = y%nthen(a*b)%n=(x*y)%n. Your expressions are all variations on that same theme.