We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The expression ((n%mod)*(n%mod))%mod is not really an application of the identity (ab)%m = ((a%m)*(b%m))%m that you as well as the top post mentions since n%mod*n%mod != n for n>mod.
If you wanted to use this identity, you would have to do it for a=sqrt(n), b=sqrt(n) - ((sqrt(n)%mod)*(sqrt(n)%mod))%mod, or any other a and b that satisfy the a*b=n equation.
The reason why it works here is due to the fact that for a*b=c, c%mod = ((a%mod)*(b%mod))%mod and that's the property that should be referred to when applying ((n%1000000007)*(n%1000000007)%1000000007) expression.
Note that for a non-prime integer n, there are some integers a, b for which n=a*b is true but when n is prime, a=1 and b=n which doesn't simplify anything.
All in all both identies look similar but there's a subtle difference worth knowing about that may save you some pain down the road.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Summing the N series
You are viewing a single comment's thread. Return to all comments →
The expression
((n%mod)*(n%mod))%mod
is not really an application of the identity(ab)%m = ((a%m)*(b%m))%m
that you as well as the top post mentions sincen%mod*n%mod != n
forn>mod
.If you wanted to use this identity, you would have to do it for
a=sqrt(n)
,b=sqrt(n)
-((sqrt(n)%mod)*(sqrt(n)%mod))%mod
, or any othera
andb
that satisfy thea*b=n
equation.The reason why it works here is due to the fact that for
a*b=c
,c%mod = ((a%mod)*(b%mod))%mod
and that's the property that should be referred to when applying((n%1000000007)*(n%1000000007)%1000000007)
expression.Note that for a non-prime integer
n
, there are some integersa
,b
for whichn=a*b
is true but whenn
is prime,a=1
andb=n
which doesn't simplify anything.All in all both identies look similar but there's a subtle difference worth knowing about that may save you some pain down the road.