Due Tuesday, April 26, 11:59 P.M.
- Overview
- Assignment
- Hints
The purpose of this lab is to introduce you to programming in Matlab.
Top
Write a pair of matlab functions phi(n) and phi2(m)
that calculate the Euler-phi function for an integer n.
The phi function is the number of integers less than n and
relatively prime to n (recall that two numbers n,k
are relatively prime if gcd(n,k)=1). So phi(12)=4
and phi(6)=2 since 1,5,7,11 are the numbers less than
12 and relatively prime to 12, and 1,5 are
the numbers less than 6 and relatively prime to 6.
Note that gcd(p)=p-1 for any prime number p. The functions should be implemented as follows:
- phi(n) should perform its calculation directly using the definition.
- phi2(n) should perform its calculation using the formula
phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pk),
where pi is prime ∀ 1≤i≤k,
n=p1e1p2e2...pkek,
and pi≠pj for i≠j.
Top
- Use as many of Matlab's builtin functions as possible to make
writing the program easier. Some functions you may find useful include
primes,gcd,sum,prod,sort,factor, and removetrailzeros.
- When writing the function phi2(n), be sure you only use
each prime divisor once. Note that the factor command returns
the factorization with multiple prime divisors repeated.
Top
Back to the course information page