1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Intuition
3.1.
Code
3.1.1.
Input
3.1.2.
Output
3.2.
Complexities
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Modulo Fermat's Theorem

Saksham Gupta
0 upvote

## Introduction

Programming is a very fun subject to study, and so is mathematics, but what happens when these two are combined? Today, we will discuss one such problem, i.e., Modulo Fermat's Theorem, where your concepts related to programming and maths would be judged. Now let's see the problem statement in detail.

## Problem Statement

We have been given two integers, â€˜Kâ€™ and â€˜M.â€™ Our task is to find the count of â€˜kâ€™ such that k < K and satisfies the equation

(modulo M). Let's understand this better by an example.

### Example

Input
M= 5
K= 4

Output
2

Explanation

We will check for every possible value of k < K

For 'k' = 1 we have a solution (1,1,2). Because we will have 1 ^ 1 + 1 ^ 1 = 2 ^ 1 which will be equal to (2 % 5) = (2 % 5) == 3.
For 'k' = 2, we don't have any solution.
For 'k' = 3 we have a solution (1,3,2). Because we will have 1 ^ 3 + 3 ^ 3 = 2 ^ 3 % 5 which will be equal to (28 % 5) = (8 % 5) == 3.
For 'k' = 4, we don't have any solution.

Thus our final count would be 2.

## Intuition

The brute force intuition is very straightforward. We will run a loop for 'k' from 1 to 'K,' and for this, we will create every possible case, i.e., we will take different values of x,y,z and check if it satisfies the equation or not. If it does, then we will increase the counter variable. Things will become more clear from the code.

### Code

``````#include <bits/stdc++.h>
using namespace std;
const int MOD = (int) 1e9 + 7;

typedef long long ll;

/* This function is used to calculate power of big numbers */
ll fpow(ll n, ll k, int p = MOD)
{
ll r = 1;
for (; k; k >>= 1) {

/* Taking MOD at necessary positions */
if (k & 1) r = r * n % p;
n = n * n % p;

}
/* Returning the value */
return r;

}
int solve(int M, long long K) {

/* This is used to avoid certain recalculations */
vector<int>arr(1e6 + 5);
int res = 0;

/* Looping over values of 'k'*/
for(int i=1;i<K+1;i++)
{
/* Initialising first M values as 0*/
for(int j=0;j<M;j++)
arr[j]=0;
for(int j=1;j<M;j++)

arr[fpow(j, i, M)] = 1;
int found = 0;

/* Creating all possible values */
for(int j=1;j<M;j++)
if (arr[j]) {
int k = (1 - j + M) % M;

/* If satisfies our equation */
if (arr[k]) {
found = 1;
break;
}
}

/* Increasing the count */
res += found;
}
return res;
}

int main()
{
int M;
long long K;

/* Taking Input */
cin>>M>>K;
cout<<solve(M,K);
}``````

#### Input

``5 4``

#### Output

``2``

### Complexities

#### Time Complexity

O(K * M), where â€˜Kâ€™ and â€˜Mâ€™ are given as input.

Reason We are first looping â€˜kâ€™ till â€˜K,â€™ which will cost us O(K) time. Inside the loop, we are finding all possible values of x,y,x, which in the worst-case costs O(M) time. Thus, the overall time complexity to O(K) + O(M) ~ O(K * M).

#### Space Complexity

O(1)

Reason: We are not using any variable space.

Also see, Euclid GCD Algorithm

## FAQs

1. What is Number Theory?
The pure branch of mathematics that deals with the study of integers and integer-valued functions is known as the number theory.

2. What are the different parts of Number Theory?
Number theory is a vast topic and consists of a large number of topics. Some of them are Prime numbers, Combinatorics as well as advanced topics such as Modular Exponentiation, Fermat's Little Theorem, Wilson's Theorem, Chinese Remainder Theorem, Euler Totient Function, Matrix Exponentiation, etc.

3. How to find the divisors of a factorial?
Steps to find the divisors of a factorial:
First, find the factorial of the given number.
Then, count the total number of divisors of the factorial.

4. What is modulo operation?
After one number is divided by another, the modulo operation yields the remainder or signed remainder of the division. A modulo N is the remainder of the Euclidean division of A by N,

5. What is the time complexity of modulo operation?
Modulo or remainder operation is an O(1) operation (it's essentially just a variation on division, which takes constant time on fixed-sized numbers).

## Key Takeaways

We saw how we solved the problem â€˜Modulo Fermatâ€™s Theorem', which was based on Number Theory. Some other problems that revolve around the number theory concepts are Finding Power of Factorial DivisorCount Prime in Ranges. Now don't waste any more time and head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more.
Till then, Happy Coding!

Live masterclass