|
|
Posted here are some comments/questions by our readers and ensuing conversations with them, related to mathematics/numbers.
Conversation with Bhaskar, who is a graduate from IIT (Kharagpur) (click to view)
Thanks to Bhaskar for initiating this conversation, that led to some detailed discussion on coprimes.
Bhaskar also shared with us the formula for sum of all coprimes, which is
Sum of all coprimes to n, which are less than n = n * phi(n) / 2.
The formula is very similar to sum of consecutive positive integers, n(n+1)/2.
Hi, i was going through Euler's Totient function and you did a magnificient job in explaining it clearly.
It helped me.
Thanks a lot.
I will be very glad if you can share the proof for phi(a.b) = phi(a).phi(b) .
Cheers,
Bhaskar.
|
Hi Bhaskar,
The proof of phi(a.b) = phi(a).phi(b), when a&b are coprime, uses Chinese Remainder Theorem.
I am still thinking of a way to prove this using some kind of array pattern just as I had
discovered the totient function.
I like to explain things in a way so that they can be visually understood.
At this point, I am able to explain the special case of the totient function's multiplicative property.
That is when a and b are prime (which means, a and b are coprime as well), then
phi(a.b) = phi(a).phi(b). This is what you came across in my article.
For example, I am explaining the case when a=5 and b=7 (both a and b are prime)
and not when we have a case like a=12 and b=5.
Before we write the proof, lets see an example of a=5 and b=7.
We want to prove that phi(5 x 7) = phi(5) x phi(7)
Note that in the case of a prime number, phi( p ) = p-1 ,
as all the numbers less than p are coprime to p.
So, RHS = (5-1) x (7-1) = 4 x 6 = 24
How about LHS. We will show that LHS is also = 24.
Here's how.
phi (5x7) = phi (35)
So we want to find all numbers coprime to 35. First, out of 35 numbers,
lets take out all multiples 5, as these are not coprime to 35.
Thats is we take out 5,10,15,20,25,30,35. Note we took out 35 here. Also note that these are 7 such numbers,
which is nothing but 35 / 5.
Now, lets take out all multiples of 7. That is 7,14,21,28,35. Note that we took out 35 again.
Also note that these are 5 in number, which is nothing but 35 / 7.
So, after we take out these numbers from 35, all remaining numbers are coprime to 35,
as they are neither multiples of 5 nor 7.
So how many such numbers are left out of 35? Lets see,
35 - (multiples of 5) - (multiples of 7) + 1 (because we took out 35 twice, we just add it once here)
OR
35 - ( 35 / 5 ) - ( 35 / 7 ) + 1
which is 35 - 7 - 5 + 1 = 23 + 1 = 24.
This matches RHS.
Now lets write a proof for this.
Claim : If p1 and p2 are prime then, phi(p1.p2) = phi(p1).phi(p2) = (p1-1).(p2-1)
Consider the product p1.p2.
The number of multiples of p1 in the product p1.p2 are (p1.p2 / p1), which is p2.
The number of multiples of p2 in the product p1.p2 are (p1.p2 / p2) which is p1.
All the numbers between 1 and p1.p2 that are NOT multiples of p1 or p2 are coprime to p1.p2.
Therefore, when we take out multiples of p1 and p2 from the numbers between 1 and p1.p2, we get,
phi(p1.p2) = p1.p2 - p1 - p2 + 1 =p1 (p2 - 1) - (p2 -1 ) = (p1-1).(p2-1) = RHS.
Hope this helps, while I try to come up with a similar proof for more general case.
Feel free to reach out for any more questions.
Thanks,
Rohit
|
Hi Rohit,
I have been trying to Google for Chinese Remainder theorem after you mentioned it.
But I could not get right material which explains it clearly.
But your explanation is awesome. Thank you very much for putting such an effort in explaining this.
Now I am able to recall a question which I used to solve by the method you mentioned above.
The question is: Find the number of numbers between 1 and 100 which are neither divisible by 3 nor 5.
( or neither by 3 nor by 7 .. like that).
This, I used to solve the same way you mentioned below.
( [ 100 - [ 100 / 3 ] - [ 100 / 5 ] + [ 100 / 15 ] ). where [p] represents the greatest integer less than or equal to n.
Also I came across a formula for sum of all those coprimes to N ( and less than N).
The formula is ( N / 2 ) * phi ( N ) . At first I could not digest the formula.
But after going through your explanation on calculating the number of coprimes to N,
It was clear that the coprimes are like mirror images from the N/2. I hope this formula helps.
Cheers,
Bhaskar.
|
Hi Rohit,
.........
I am just trying to find out the proofs whenever I come across new formulas.
And this number system is getting very interesting as I am digging deep.
Today I came across one more theorem - "Euler-Fermat theorem". It says that
P ^ phi(N) = 1 (mod N). where P and N are coprimes.
But I am not able to find a good proof for this.
This formula is being suggested to find the remainder when some big powers ( like 7 ^ ( 7 ^ 7) )
are divided by some number like 13, 16 ..
Though most part of the proof I could understand I am stuck at one point.
Let me put the proof here.
Proof:
a(1), a(2).. a(k) are coprimes of N (and less than N). Here k = phi ( N ).
Since P and N are coprimes,
P * a(1) , P * a(2) , P * a( 3 ) ....... are coprimes of N.
But in the next line I am stuck.
It says that if we take the product of above numbers and divide it by N,
then the remainder will be same as the product of remainders
we get by dividing a(1) , a(2) , a(3) ..... by N.
That means ,
[ P*a(1) * P*a(2) * P*a(3) ..... P*a(k) ] (mod N) = [ a(1)(mod N) * a(2)(mod N) ....... a(k) ] (mod N).
after that is simple.
If possible, can you explain this line.
Cheers,
Bhaskar
---------------------------------------------------
By the way,
I forgot to post the link for the proof.
http://planetmath.org/?op=getobj&from=objects&id=335
Thanks,
Bhaskar.
|
Hi Bhaskar,
I had not read the proof you sent me earlier, as I wanted to spend a couple of days trying to prove it in my own way,
but concluded that it is difficult to find a simple proof, without going into too many steps.
So I decided to go back to the proof you sent.
I am attempting to explain this proof (and the line you did not understand).
Lets start with an example. Lets say N is 10, in our case, and P is, say 13, a number coprime to 10.
1) Lets talk about N first. The numbers coprime to 10 are 1,3,7 & 9.
When we divide any number by 10, the possible remainders are 0 thro 9.
1,3,7 & 9 are a part of this remainder set.
Lets call a1=1, a2=3, a3=7, a4=9.
2) Now lets see the relation between P and N.
The important part to understand here is what remainder we can get when we divide P by N.
Also, this is the part that is ommited from the proof you sent me - the relation between P and N.
P and N are coprime.
Which means P is NOT a multiple of N. Which means when we divide P by N, we should get a non-zero remainder.
Since N is 10, we can get remainders 1 thro 9.
However, since P is coprime to N (i.e 10), the remainder when P is divided by N should also be coprime to 10.
That is, the remainders should be one of 1,3,7 & 9 (or a1, a2, a3 or a4). Why?
Lets say the remainder of P mod N is something like 2, which is not coprime to 10.
Which means, the number P is of the form (10 times something) + 2. Lets call this something as m.
That is P = 10*m + 2 = 2(5*m+1).
Which would mean gcd of P and N is 2, and not 1. Which is a contradiction.
So, remainder left by P when divided by N, must be coprime to N.
That is, the remainder of P divided by N must be one of 1,3,7,9, as per our example.
In other words, if N is 10, P could be one of 11,13,17,19,21,23,27,29.. etc.
That is P must of types (N*m + a1) or (N*m + a2) or (N*m + a3) or (N*m + a4).
P *cannot* be of *any other* type.
We chose P as 13 for our example (of type N*m + a2).
3) Now lets see what happens when we multiply P, with each of 1,3,7 & 9.
That is P*a1, P*a2,P*a3 and P*a4.
We are checking what is the remainder term for each product.
Lets multiply P with a1.
13 * a1 = 13 * 1 =13 and remainder is 3, which is a2. That is
P*a1 =~ a2 (mod N) ------------ (1)
Again,
13 * a2 = 13 * 3 =39 and remainder is 9, which is a4
Hence. P*a2 =~ a4 (mod N) -------------- (2)
Similarly,
13 * a3 = 13 * 7 = 91 and remainder is 1, which is a1.
Hence, P * a3 =~ a1 (mod N) -------------- (3)
Also,
13 * a4 = 13 * 9 = 117 where remainder is 7, which is a3.
Hence, P * a4 =~ a3 (mod N) -------------- (4)
So the important thing to note here is that, if we consider products P*a1,P*a2,P*a3,P*a4,
they leave a residue of a2, a4, a1 and a3. ie. we get all numbers a1, a2, a3, a4 back as remainders,
though not in that order.
Now, in our case, P was 13, that is, of the form (N*1 + a2).
Even if P was either 11 or 13 or 19 (ie. N*1 + a1, N*1 + a3, or N*1 + a4),
we would still get back the a1, a2, a3, a4 as the remainders, in different orders.
There is kind of a circular relationship between (P*a1, P*a2, P*a3,P*a4) and (a1, a2, a3, a4).
(I would like to mention here that this is where I was stuck!
I wanted to prove that no matter what the type of P,
we will always get back a1,a3,a3,a4 in some order, after multiplying them with P.
However, this is kind of "assumed" in the proof.)
Using modulo arithmetic, from (1), (2), (3) & (4), we get
P*a1.P*a2.P*a3.P*a4 =~ a1*a2*a3*a4 (mod N) --------- (5)
This is the line you mentioned to me.
The line you sent to me uses "equals" sign and the line above uses "congruence" sign.
Otherwise, both mean the same.
#############
The line you sent me is
[ P*a(1) * P*a(2) * P*a(3) ..... P*a(k) ] (mod N) = [ a(1)(mod N) * a(2)(mod N) ....... a(k) ] (mod N).
On RHS, we have { (a1 mod N)*(a2 mod N) ... (ak mod N) } (mod N )
Note that since a1, a2..are all less than N, a1 (mod N) = a1 , a2 (mod N) = a2...
That is, if you divide 1,3,7,9 by 10, the remainders are 1,3,7,9. Quotient is 0.
Hence RHS is nothing but a1*a2*a3*a4 (mod N), same as RHS of (5).
#############
Rest of the proof, you have followed already.
Hope this helps. If u still did not get any part of this, do let me know.
Regards,
Rohit
|
Hi Rohit,
Your explanation is great.
The point that P can be only of the form (N*m + a1) or (N*m + a2) or (N*m + a3) or (N*m + a4) is well deducted.
And the fact that remainders will be rotating is also good.
Thanks man.
But for the time being, I will be focusing more on practice and give a break for proofs....
Will post you more theorems in future. I still have some theorems at hand to do research.
Cheers,
Bhaskar
|
|