NUMBER THEORY Problem – Last 4 Digits

Number Theory is the most important topic while preparing for Mathematics Olympiad. Here we provide guidance for solving Number Theory problems with clarity on concepts. Here we provide different typical problems and solve them step by step clearing the concepts involved in the problem.

Here the Number Theory problem & solution for finding the last 4 digits of a large exponential number such as 7893^7893 is give as below. The answer is 8293. We will go step by step solution to it. We also provided here the interactive screen for you to get acquainted for solving these problems at the end of this solution. Use the written concepts and interactive screen to get a feel of solution on your own.

Number Theory Problem – Problem statement

Find the last four digits of a large exponential number ${7893}^{7893}$.

Concepts involved

The various concepts required to be understood for solving the above problem are :

1. Prime factorization
2. Euler Totient Function
3. Modular arithmetic
4. Euler Theorem
5. Exponent Decomposition

Step by step Solution

For this Number Theory Problem, the step by step solution for the above problem is given here using above concepts.

For finding last four digits of any number N how large it may be, we have to find out mod(10000) of that number.

Hence here we have to find out ${7893}^{7893}$ (mod 10000 ).

From the principles of prime factorization,

10000= 16×625 = $2^4\times 5^4$ where 2 and 5 are prime numbers.

Here we apply the Euler Totient function concepts.

As per Euler Totient function , number N can be expressed as product of distinct primes as,

$N=p_1{p}_2\dots$ , then the Euler Totient function is given as

$\mathit{\phi }(n)=n(1-\frac{1}{p_1}\mathrm{)(}1-\frac{1}{p_2}\mathrm{)\dots .}$

For 10000= 16×625 = $2^4\times 5^4$ ,

$\mathit{\phi }(10000)=10000(1-\frac{1}{2}\mathrm{)(}1-\frac{1}{5})=4000$

From Euler theorem,

If $\gcd (a,n)=1,\mathrm{then},a^{\mathit{\phi }(n)}\equiv 1(\mathrm{mod}n)$

Here gcd(10000,7893)=1, hence,

${7893}^{4000}\equiv 1(\mathrm{mod}10000)$

But ${7893}^{7893}={7893}^{3893}\times {7893}^{4000}$ , hence

${7893}^{7893}\equiv {7893}^{3893}(\mathrm{mod}10000)$

The exponent 3893 = 2048+1024+512+256+32+16+4+1

${7893}^{3893}\equiv {7893}^{2048}.{7893}^{1024}.{7893}^{512}.{7893}^{256}.{7893}^{32}.{7893}^{16}$. ${7893}^4.{7893}^1$

Fin the last four digits of all above using the method of sequentially,

$\begin{array}{c}{7893}^1=7893,\\ {7893}^2=7893\times 7893=62299449\Rightarrow 9449\\ {7893}^4=9449\times 9449=89283601\Rightarrow 3601\end{array}$

$\begin{array}{c}{7893}^8=3601\times 9449\Rightarrow 7201,\\ {7893}^{64}\Rightarrow 7601\\ {7893}^{128}\Rightarrow 5201\\ {7893}^{256}\Rightarrow 0401\\ {7893}^{512}\Rightarrow 0801\end{array}$

By continuing the process we get,

$\begin{array}{c}{7893}^{1024}\Rightarrow 1601\\ {7893}^{2048}\Rightarrow 3201\end{array}$

By continuing the above procedure and taking last four digits of multiplication of all above 4 digits one bt one we get,

$\begin{array}{c}3201\times 1601\Rightarrow 4801,\\ 4801\times 0801\Rightarrow 5601\\ 5601\times 0401\Rightarrow 6001\end{array}$

$\begin{array}{c}6001\times 8801\Rightarrow 4801\\ 4801\times 4401\Rightarrow 9201\\ 9201\times 3601\Rightarrow 2801\\ 2801\times 7893\Rightarrow 8293\end{array}$

Hence the last four digits of ${7893}^{7893}$ is 8293.

Hence the answer is 8293.

Some values are intentionally jumped . These intermittent values have to be found out by the reader. Mathematics can be understood by practice only. Hence the intermittent few calculations are left out as Home Work for the reader to understand the process well.

The Number Theory problem can be solved with intuition rather than mechanical formulae substitution. Hence fo solving the Number Theory problem like this I encourage reader to develop logical approach to solution and practising it regularly.

For any clarifications aon above solution , kindly write to us at : https://mathsnscience.com/contact/

The video lectures on this type of questions and concepts are available in YouTube channel maths&science by iitian.

The link for the channel is : https://www.youtube.com/@mathsciencebyiitian

The above problem solution in video form can be accessed here :

Interactive Solution

The interactive solution for the problem is given as below for your participation in the solution and better understanindg the process.

Best of luck everybody