max_kibble's blog

[UVALive-3722] Why does Fermat's little theorem fail?
By max_kibble, history, 5 years ago, In English

Hello codeforces, recently i solved this problem.

Generally speaking, given four integers x,a,n,c, c is a prime number.

You are asked to calculate f(n)%c:

$$$ f(0)=x\\ f(n)=a\cdot (f(n-1)-1) $$$

which leads to:

$$$ f(n)=a^n\cdot x - (a+a^2+a^3+...+a^n)=a^n\cdot x-\frac{a\cdot (a^n-1)}{a-1} $$$

The key part is the fraction part. At first, I tried to solve the problem with binary exponentiation and Fermat's little theorem. I noticed that in this problem a-1 could be times of c and took care of the condition in implementation. However, the submission is verdict as WA. Later, I tried another way to calculate the fraction and got accepted.

But I'm still puzzled about why Fermat's little theorem failed in this problem. As the online judge website didn't provide test cases, I randomly generated over 100,000 test cases. There are no differences between outputs of the two submissions.

For clarity, here are my two submissions.

Here is my WA submission: submission_1

Here is my AC submission: submission_2

Thanks in advance.

Conclusion

The input data of this problem is wrong, which contain test cases with c not a prime.

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by max_kibble (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Sorry if I'm wrong, but shouldn't the formula be like:

$$$f(n) = (a^n* x) - (\dfrac{a^{n + 1} - 1}{a - 1} - 1) $$$

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is no fail in Fermat's theorem. It's said that $$$p\ is\ prime\ AND\ a\ mod\ p\ !=\ 0\ => a^{p - 1} \equiv 1 (mod p)$$$.
As you said $$$a - 1$$$ can be dividable by $$$c$$$ so you just can't use there this theorem since conditions aren't satisfied.

You have fraction $$$\frac{a(a^n-1)}{a-1}$$$. You know this is integer number so if $$$a-1$$$ is dividable by $$$c$$$ then numerator is dividable by $$$c$$$ too. So in your WA solution fraction always calculated as zero. Of course there is countertest: $$$c = 3,\ a = 10,\ n = 1$$$. Fraction is equal to 10 and correct result must be 1 (10 mod 3 = 1).

I don't know easier way to calculate correct fraction then your binary summation.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually in my WA submission, I did not use Fermat's little theorem when $$$a-1$$$ is dividable by $$$c$$$. In such condition, $$$a\equiv 1\ (mod\ c)$$$. Thus I use the sum $$$a+a^2+...+a^n$$$ instead of the fraction. Here is what I did in my code:

    // A is the ax^n part
if ((a - 1) % c == 0) {
  assert(A == x % c);
  ans = A - n % c;
}
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      And what you trying to do there? Just assume that fraction is equal to $$$n$$$? That's not correct too. And assert can fail since $$$A = (x * a^n)\ mod\ c$$$ and this is not always equal to $$$x\ mod\ c$$$.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In my understanding, if $$$a\equiv 1\ (mod\ c)$$$:

        1. $$$a+a^2+...+a^n\equiv 1+1+...+1\equiv n\ (mod\ c)$$$. And the fraction equals the summation.

        2. Why does $$$x\cdot a^n\equiv x\ (mod\ c)$$$ fail when $$$a\equiv 1\ (mod\ c)$$$

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          You absolutely right

          In short: as I see there is test where $$$c$$$ is not prime. That's why your second solution works: it relies only on multiplicative and summative operations which are independent of "module primality".

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by max_kibble (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by max_kibble (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Probably $$$a < c$$$ doesn't hold. You can just use divide and conquer to calculate that sum.

→ Reply