==> ?(4) x ?(5) = 2 x 4 = 8
? ?(4x5) = ?(4) x ?(5)
Ex 4. When n = 4 and m = 6, we want to check whether ?(4 x 5) is or is not
equal to ?(4) x (6). ?(4x6) can also be written as ?(24). We already know from previous
questions that ?(24)= 12, ?(4) = 2 and ?(6)=2
==> ?(4) x ?(6) = 2 x 2= 4, but 12 ? 4
? ?(4x6) ? ?(4) x ?(6)
Ex5. When n = 4 and m = 8, we want to check whether ?(4 x 8) is or is not
equal to ?(4) x (8). ?(4x8) can also be written as ?(32).
n 32
Co prime1,3,5,7,9,11,13,15
with n 17,19,21,23,25,27,29
?(n) 15
We know from the table that ?(32) = 15, and we already know from previous
questions that ?(4)= 2 and that ?(8)=4
==> ?(4) x ?(8) = 2 x 4= 8, but 32 ? 8
? ?(4x8) ? ?(4) x ?(8)
Ex6. When n = 4 and m = 10, we want to check whether ?(4 x 8) is or is not
equal to ?(4) x (10). ?(4x10) can also be written as ?(40).
n 10 40
Co prime 1,3,7,9 1,3,7,9,11,13,17,19,21
with n 23,27,29,31,33,35,37,39
?(n) 4 17
We know from the table that ?(40) = 17, and that ?(10) = 4, we also already know
from previous questions that ?(4)= 2
==> ?(4) x ?(10) = 2 x 4= 8, but 40 ? 8
? ?(4x10) ? ?(4) x ?(10)
3) When p is prime we must find an expression for ?(p). We already know that ?(2) =
1 , ?(3)= 2 , ?(5)=4 , ?(7)=6 and that ?(11)=10. Two more prime numbers are 13 and 17:
n 13 17
Co prime 1,2,3,4,5,6,7,8 1,2,3,4,5,6,7,8,9,10
with n 9,10,11,12,13, 11,12,13,14,15,16 ?(13)=12 , ?(17)=16
?(n) 12 16
p 2 3 5 7 11 13 17
p-1 1 2 4 6 10 12 16
?(p) 1 2 4 6 10 12 16
From the table above, we notice that ?(p) = p-1, this is true as the highest common factor of
a prime number has to be one, therefore leaving us with all the terms below p when finding
the phi function of a prime number.
The expression for ?(p) is: ?(p) = p-1
4) In some cases ?(n x m) = ?(n) x ?(m), whilst in other cases ?(n x m) ? ?(n) x ?(m). To
investigate this we may begin with several examples, changing one variable at a time and
then look for a common link.
n=2
If m =2, we must check whether or not ?(2 x 2) = ?(2) x ?(2),
?(2) x ?(2) = 1 x 1=1, ?(2 x 2) = ?(4)=2, but 2?1
? ?(2 x 2) = ?(2) x ?(2)
If m =3, we must check whether or not ?(2 x 3) = ?(2) x ?(3),
?(2) x ?(3) = 1 x 2=2, ?(2 x 3) = ?(6)=2, 2=2
? ?(2 x 3) = ?(2) x ?(3)
If m =4, we must check whether or not ?(2 x 4) = ?(2) x ?(4),
?(2) x ?(4) = 1 x 2=2, ?(1 x 2) = ?(2)=1, but 2?1
? ?(2 x 4) ? ?(2) x ?(4)
If m =5, we must check whether or not ?(2 x 5) = ?(2) x ?(5),
?(2) x ?(5) = 1 x 4=4, ?(2 x 5) = ?(10)=4, 4=4
? ?(2 x 5) = ?(2) x ?(5)
If m =6, we must check whether or not ?(2 x 6) = ?(2) x ?(6),
?(2) x ?(6) = 1 x 2=2, ?(2 x 6) = ?(12)=4, 4?2
? ?(2 x 6) ? ?(2) x ?(6)
If m =7, we must check whether or not ?(2 x 7) = ?(2) x ?(7),
n 14
Co prime 1,3,5,9,11,13
with n
?(n) 6
?(2) x ?(7) = 1 x 6=6, ?(2 x 7) = ?(14)=6, 6=6
? ?(2 x 6) = ?(2) x ?(6)
n=3
If m =3, we must check whether or not ?(3 x 3) = ?(3) x ?(3),
n 9
Co prime 1,2,4,,5,7,8
with n
?(n) 6
?(3) x ?(3) = 2 x 2=4, ?(3 x 3) = ?(9)=6, 4?6
? ?(3 x 3) ? ?(3) x ?(3)
If m =4, we must check whether or not ?(3 x 4) = ?(3) x ?(4),
?(3) x ?(4) = 2 x 2 =4, ?(3 x 4) = ?(12)=4, 4=4
? ?(3 x 4) = ?(3) x ?(4)
If m =5, we must check whether or not ?(3 x 5) = ?(3) x ?(5),
n 15
Co prime 1,2,4,7,8,11,13,14
with n
?(n) 8
?(3) x ?(5) = 2 x 4=8, ?(3 x 5) = ?(15)=8, 8=8
? ?(3 x 5) = ?(3) x ?(5)
If m =6, we must check whether or not ?(3 x 6) = ?(3) x ?(6),
n 18
Co prime 1,5,7,11,13,17
with n
?(n) 6
?(3) x ?(6) = 2 x 2 =4, ?(3 x 6) = ?(18)=6, 6?4
? ?(3 x 6) ? ?(3) x ?(6)
n=4
If m =4, we must check whether or not ?(4 x 4) = ?(4) x ?(4),
n 16
Co prime 1,3,5,7,9,11,13,15,
with n
?(n) 8
?(4) x ?(4) = 2 x 2 =4, ?(4 x 4) = ?(16)=8, 8?4
? ?(4 x 4) ? ?(4) x ?(4)
If m =5, we must check whether or not ?(4 x 5) = ?(4) x ?(5),
?(4) x ?(5) = 2 x 4 =8, ?(4 x 5) = ?(20)=8, 8=8
? ?(4 x 5) = ?(4) x ?(5)
If m =6, we must check whether or not ?(4 x 6) = ?(4) x ?(6),
?(4) x ?(6) = 2 x 2 =4, ?(4 x 6) = ?(24)=8, 8?4
? ?(4 x 6) ? ?(4) x ?(6)
After completing a series of examples we may illustrate our results graphically(- means as
above):
Values of Specific series of Does m=nr ( where r is an Are n and m Does ?(n x m)
n and m numbers investigated integer)? (or n=mr if n?m) co-prime? Equal ?(n) x?(m)?
2,2 when n=m yes no no
3,3 - yes no no
4,4 - yes no no
2,4 when n and m are even yes no no
4,6 - yes no no
2,3 When m-n or n-m=1 no yes yes
3,4 - no yes yes
4,5 - no yes yes
2,5 When n and m are prime no yes yes
(other than already mentioned)
2,7 - no yes yes
3,5 - no yes yes
m=nr is derived from n by the use of cross-multiplication:
m
i.e. If n = 2 and m=4. 2 = 0.5, when cross-multiplying we get 2= 4 x 0.5
4
==> 4 = 2 , the reciprocal of 0.5 = 1 = 2 ==> 4= 2 x 2 ? (in this case) m=nr
0.5 0.5
However the limitations of the formula are that the denominator must be greater than the
numerator for r to be an integer, so if m is larger than n we place m as the numerator and
thus obtain the formula n=mr.
It may be suffice to say that when n divided by m gives us m=rn(or m divided by n,
if n is greater than m, gives us m=nr), where r is an integer, than since m and n are not co-
prime (they cannot be co-prime if n is a multiple of m, or vice versa) therefore ?(nxm) ?
?(n) x ?(m).
When n divided by m does not give us n=mr(or opposite-refer to limitations), for
example when n=3 and m=5:
5 divided by 3 =1.67(to 3.s.f), by cross multiplication 3x1.67=5 ==> 3= 5 divided by 1.67,
the reciprocal of 1.67=0.6(to 1.d.p) ==> 3=5x0.6, r=0.6, but 0.6 is not an integer ? n ? mr
,than n and m must be co-prime (since n and m are not multiples). If n and m are co-prime
than, as seen in the table, ?(nxm) = ?(n) x ?(m).
Only when the only common factor between n and m is one, i.e n and m are co-prime,
?(nxm) = ?(n) x ?(m). Therefore:
?(nxm) = ?(n) x ?(m) when (n , m) = 1
5)i. When p is prime we must find the general result for ?(p2). Using four
examples we may try and identify a correlation:
n 25 49
Co prime 1,2,3,4,6,7,8,9,11,12,13,14, 1,2,3,4,5,6,8,9,10,11,12,13,15,16,17,18,19,20,22,23, 24,25,26,27
with n 16,17,18,19,21,22,23,24 29,30,31,32,33,34,36,37,38,39,40,41,43,44,45,46,47,48
?(n) 20 42
p p2 ?(p2) (p-1) p(p-1)
2 4 2 1 2x1=2
3 9 6 2 3x2=6
5 25 20 4 5x4=20
7 49 42 6 7x6=42
From the above results we notice that ?(p2)=p(p-1)
In general : ?(p2)=p(p-1)
From the laws of indices we know that p(p-1) is the same as p2 - p,
therefore ?(p2) is also equal to p2 - p i.e. ?(32) = 9 - 3 = 6
ii.When p is prime we must find the general result for ?(p3)
n 27 125 343
Co prime 1,2,4,5,7,8,10,11,13,14,16,17, ?(25)=20 125 divided by 25=5 343divided by 49=7,?(49)=42
with n 19,20,22,23,25,26 20x5=100 42x7=294
?(n) 18 100 294
p p3 ?(p3) p2 ( p-1) p2(p-1)
2 8 4 4 1 4x1=4
3 27 18 9 2 9x2=18
5 25 100 25 4 25x4=100
7 343 294 49 6 49x6=294
From the above results we notice that ?(p3)=p2 (p-1)
In general : ?(p3)= p2(p-1)
From the laws of indices we know that p2(p-1) is the same as p3 - p2,
therefore ?(p3) is also equal to p3 - p2 i.e.?(33) = 27 - 9 = 18
iii. p n pn ?(pn) pn-1 p-1 pn-1(p-1)
2 2 4 2 2 1 2x1=2
3 2 9 6 3 3 3x2=6
5 2 25 20 5 5 5x4=20
7 2 49 42 7 6 7x6=42
2 3 8 4 4 1 4x1=4
3 3 27 18 9 2 9x2=18
5 3 125 100 25 4 25x4=100
7 3 343 294 49 6 49x6=294
2 4 16 8 8 1 8x1=8
3 4 81 54 27 2 27x2=54
5 4 625` 500 125 4 125x4=500
2 5 32 16 16 1 16x1=16
3 5 243 162 81 2 81x2=162
We already know that ?(p2)=p(p-1) and that ?(p3)=p2 (p-1) from
the previous question. From the table we also notice that ?(p4)=p3 (p-1)
and that ?(p5)= p4(p-1). From looking at all these results we may say that,
where n is an integer; ?(pn)=pn-1(p-1)
In general: ?(pn)= ?(pn)=pn-1(p-1)
We may also say, by multiplying out pn-1(p-1) that it equals pn - pn-1 , therefore ?(pn) also
equals pn - pn-1 i.e ?(23) = 8 - 4 = 4
pn-1(p-1) can also be expressed as pn (p-1) ==> pn+1 - pn i.e. ?(23) = 24 - 23
p p 2
==> 16 - 8 = 4
2
However if n is not a positive integer then the general solution is not applicable.
p n pn
2 -2 0.25
3 -2 0.11
2 -.5 0.71
2 .5 21/2= ?2=1.414
3 .5 31/2= ?3=1.732
5 .5 51/2= ?5=2.236
2 1/3 21/3= 3?2=1.260
3 1/3 31/3= 3?3=1.442
5 1/3 51/3= 3?5=1.710
From the results above, we notice that when n is not a positive integer: if n is a
fraction, pn is an irrational number (not a positive integer) and if n is negative pn is also not a
positive integer. Since the phi-function, from its definition, is only applicable to positive
integers, when n is a fraction or negative;
?(pn)??(pn)=pn-1(p-1) because ?(pn) is un-obtainable.
6) When p and q are different prime numbers, than the common factor between them is
always one i.e. they are co-prime for example 2,3,5,7,are all co-prime(from question4).
Therefore ( also from question 4,where p and q are different prime numbers):
?(pxq) = ?(p) x ?(q)
To progress any further we must check whether or not ?(pn x qm ) = ?(pn) x ?(qm).
This can be done quicker by checking whether or not pn and qm are co-prime.
p q n m pn qm Are pn and Are pn and qm
qm multiples co-prime
2 2 1 1 2 2 yes no
2 3 1 1 2 3 no yes
2 2 2 1 4 2 yes no
2 3 2 2 4 9 no yes
2 3 2 3 4 27 no yes
5 11 3 6 125 1771561 no yes
7 3 2 2 49 6 no yes
From the table, we notice that pn and qm are co-prime when p and q are different
prime numbers (as mentioned before n and m must be positive integers so that pn and qm are
also positive integers). Therefore if p?q and n and m are positive integers then pn and qm
are co-prime and therefore:
?(pn x qm ) = ?(pn) x ?(qm), but ?(pn)=pn-1(p-1) and ?(qm )=qm-1 (q-1) (from 5)
? ?(pn x qm ) = pn-1(p-1) qn-1 (q-1)
==> ?(pn x qm ) = (pn - pn-1) (qm - qm-1) = pn qm - pn qm-1 - pn-1 qm + pn-1 qm-1
The general result for?(pn x qm ) is:
Equation1: ?(pn x qm ) = pn qm - pn qm-1 - pn-1 qm + pn-1 qm-1
The general result can also be expressed differently if we take pn-1(p-1) and qm-1 (q-1) to
equal pn+1 - pn and qn+1 - qn respectively (from 5).
p q
? ?(pn x qm ) = pn+1 - pn x qn+1 - qn = pn+1 qm+1 - pn+1 qm - pn qm+1 + pn qm
p q pq
The general result for?(pn x qm ) is also:
Equation2: ?(pn x qm ) = pn+1 qm+1 - pn+1 qm - pn qm+1 + pn qm
pq
It may be important to mention that Equation 1? Equation 2
Another way of expressing Equation one is to express q as the base p, and thus
upon multiplying, the powers are added. To do this we use logarithms. A logarithm, is the
power to which the base, is raised to yield a specific number. For example, in the expression
102 = 100, the logarithm of 100 to the base 10 is 2. This is written log10 100 = 2. To
express 5 as the base 3 we write: 3log5 /.log3, however this is only an approximation as
log5/log3 gives an irrational number; rational to the power of irrational gives irrational, but
we may say that it is correct to one decimal place.
And thus: p x q is approximately equal to plog q /.log p x p ? pn x qm is approximately
equal to ( plog q /.log p)m x p n
==> pn + m log q/log p ,
pn qm - pn qm-1 - pn-1 qm + pn-1 qm-1 ==> pn + m log q/log p - pn + (m-1 x log q/log p)
- pn-1 + m log q/log p + pn-1 + (m-1 x log q/log p)
Equation 3: ?(pn x qm ) = pn + m log q/log p - pn + (m-1 x log q/log p)
- pn-1 + m log q/log p + pn-1 + (m-1 x log q/log p)
i. To obtain ?(36) we must first factorize it :
36 2
18 2
9 3
1 3
? ?(36) = ?(22 x 32)
Using equation 1:?(22 x 32)=(4x9) - (2x9) - (3x4) + 6 = 36 -18 -12 + 6 =12
Using equation 2:?(22 x 32)=(23 x 33 - 23 x 32 - 22 x 33 + 22 x 32) / 2 x 3
= 216 - 72 -108 + 36 / 6 = 72/6 =12
Using equation 3:?(22 x 32)= 22+(2 x log3/log 2) - 22+ log3/log 2 -21 +(2 x log3/log 2)
+21+log3/log 2 is approximately equal to 36 -18 -12 + 6 =12
? ?(36) = 12
ii. To obtain ?(200) we must first factorize it :
200 2
100 2
50 2
25 5
5 5
? ?(200) = ?(23 x 52)
Using equation 1:?(23 x 52)= (25 x 8) - (25 x 4) - (5 x 8) + (5 x 4)= 200-
100-40+20= 80
Using equation 2:?(23 x 52)= (24 x 53 - 24 x 52 - 23 x 53 + 23 x 52) /2x5 =
(2000 - 400 -1000 + 200) / 10 = 800 / 10 = 80
Using equation 3:?(23 x 52)= 23+(2 x log5/log 2) - 23+ log5/log 2 -22 +(2 x log5/log 2)
+22+log5/log 2 is approximately equal to 200-40-100+20= 80
? ?(200) = 80
iii. To obtain ?(19600) we must first factorize it :
19600 2
9800 2
4900 2
2450 2
1225 5
245 5
49 7
7 7
?(19600) = ?(24 x 52 x 72)
We already know that ?(pn x qm ) = ?(pn) x ?(qm), now what we need to do is
investigate whether or not ?(pn qm sm) = ?(pn qm) x ?(sm) , where p, q,
and s are different prime numbers. This can be done by investigating
whether the product of pn qm is co-prime with sm:
p q s n m pn qm sm Is pn qm co-prime with sm
1 2 3 2 3 8 27 yes
2 3 5 2 3 108 125 yes
7 3 5 5 6 12252303 15625 yes
2 5 7 4 2 400 49 yes
5 7 11 3 5 2100875 161051 yes
Since pn qm is co-prime with sm, from question 4 we know that ?(pn qm sm) = ?(pn qm) x
?(sm). For example:
n 20
Co prime 1,3,7,9,11 n 60
with n 13,17,19 ?(60) = ?(20) x 3=24
?(n) 8 ?(n) 24
When p=2 q=3, s=5, n=2 and m=1
?(4x3x5) = ?(60)=24
?(2x9)=?(18)=6, ?(5) = 4, ==> 24= 6 x 4
? ?(pn qm sm) = ?(pn qm) x ?(sm)
Given that we know ?(pn qm sm) = ?(pn qm) x ?(sm), to obtain ?(19600) we therefore have
to multiply the equations we obtained earlier with ?(sm). Since S is prime, we know from
question four that:
?(sm) = sm-1(s -1) = (sm - s m-1) ? sm+1 - sm therefore we multiply by (sm - s m-1)
or sm+1 - sm s
s
From Equation 1 ?(pn qm sm) is: (we may call it Equation 1a)
?(pn qm sm)=(pn qm - pn qm-1 - pn-1 qm + pn-1 qm-1) x (sm - s m-1)
The above may be expanded by multiplying out the brackets to give:
Equation 1b: ?(pn qm sm)= (pn qm sm ) - (sm pn qm-1) -
(sm pn-1 qm) + (sm pn-1 qm-1) - (s m-1 pn qm) +
(s m-1 pn qm-1) + (s m-1 pn-1 qm) - (s m-1 pn-1 qm-1)
Note that Equation 1a?Equation 1b
From Equation two we get Equation 2a:
?(pn qm sm)= pn+1 qm+1 - pn+1 qm - pn qm+1 + pn qm x sm+1 - sm
pq s
Equation 2a may be expanded to give Equation 2b:
?(pn qm sm)= (sm+1 pn+1 qm+1 - sm+1 pn+1 qm - sm+1 pn qm+1 + sm+1 pn qm
- sm pn+1 qm+1 + pn+1 qm sm + sm pn qm+1 - pn qm sm) / pqs
Note that Equation 2a ? Equation 2b
Equation 1a can also be written differently if we express q and s in terms of the base p:
Equation 3a:
?(pn qm sm)= pn + m log q/log p + m log s/log p - pn + (m-1 x log q/log p)+m log
s/log p
- pn-1 + m log q/log p + m log s/log p + pn-1 + (m-1 x log q/log p) + m log s/log p - pn
+ m log q/log p + (m-1 x log s/log p) + pn + (m-1 x log q/log p)+(m-1 x log s/log p) + pn-1
+ m log q/log p + m-1 log s/log p - pn-1 + (m-1 x log q/log p) + (m-1 x log s/log p)
(note the above is only an approximation)
Using Equation 1a:
?(24 x 52 x 72)= (400 - 80 - 200 + 40) x (49 - 7) = 160 x 42 = 6720
Using Equation 1b:
?(24 x 52 x 72)= (24 x 52 x 72) - (72 x 24 x 5) - (72 x 23 x 52) + (72 x 23 x 5)
- (7 x 52 x 24) + (7 x 24 x 5) + (7 x 23 x 52) - (7 x 23 x 5) = 19600 - 3920 -
9800 +1960 - 2800 + 560 + 1400 - 280 = 6720
Using Equation 2a :
?(24 x 52 x 72)= 25 x 53 - 25 x 52- 24 x53 + 24 x 52 x 73-72
2 x 5 7
= 160 x 42 = 6720
Using Equation 2b :
?(24 x 52 x 72)= (73 x 25 x53 - 73 x 25 x 52 - 73 x24 x53 + 73 x24 x 52 - 72 x
25 x53 + 72 x 25 x 52 + 72 x 24 x53- 72 x24 x 52) / 2 x 5 x 7 = 470400 / 70
= 6720
Using Equation 3a :
?(24 x 52 x 72)= 24 + 2 x log 5/log 2 + 2 x log 7/log 2 - 24 + (1 x log 5/log 2)+2 log 7/log 2 - 23 + 2 x
log 5/log 4 + 2 log 7/log 2+ 23 + (1 x log 5/log 2) + 2 log 7/log 2 - 24 + 2 x log 5/log 2 + (1 x log 7/log 2) + 24 +
(1 x log 5/log 2)+(1 x log 7/log 2) + 23 + 2 log 5/log 2 + 1 x log 7/log 2 - 23 + (1 x log 5/log 2) + (1 x log 7/log 2)
is approximately equal to 19600 - 3920 - 9800 +1960 - 2800 + 560 + 1400
- 280 = 6720
? ?(19600) = 6720
"Function," Microsoft (R) Encarta. Copyright (c) 1994 Microsoft Corporation. Copyright (c) 1994 Funk
& Wagnall's Corporation.
"Logarithm," Microsoft (R) Encarta. Copyright (c) 1994 Microsoft Corporation. Copyright (c) 1994
Funk & Wagnall's Corporation.
1
