Euler_Phi and Its Applications

Euler_Phi, the LCM method and the Squaring method


Updated 7 Jun 2005

No License is a suite of the foll Programmes :

1) Euler_Phi (n) returns the no of positive integers less than n which are prime to n.

2) a_k_mod_m_LCM_Method (a, m, k) : Imagine computing mod(14^26, 45) or mod(56^3005, 1125).
This programme computes a_k_mod_m = mod (a^k, m) when a and m are coprime, using certain rules for the reduction of computations based on Euler_Phi.

3) b_n_mod_m_Rpt_Sq_Method (b, n, m) : Imagine computing mod(38^75, 103) or mod(38^75, 103). This programme computes b_n_mod_m = mod (b^n, m).
The diff between this pgm and a_k_mod_m_LCM_Method.m is that in a_k_mod_m_LCM_Method,
the inputs a and m are coprime ; here, in b_n_mod_m_Rpt_Sq_Method.m, it is not necessary that b and m need be coprime.

4) Verify_Euler_Phi(n) : This is a small programme to prove that n = sum of Euler_Phi taken over all divisors d of n.

Refer to Euler_Phi function in P15, P22, P23, Prob 21 & Prob 23 / (P26 + P205) in the book : A course in Number Theory and Cryptography by Neal Koblitz.

Cite As

Sundar Krishnan (2023). Euler_Phi and Its Applications (, MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R14
Compatible with any release
Platform Compatibility
Windows macOS Linux
Find more on Sequence and Numeric Feature Data Workflows in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes

I have added some more comments and explained Prob 21b of NK book in more detail.