[number theory] product of co primes congruent to 1 (mod m)

In summary, the goal of this proof is to find a set of integers that cancel each other out when multiplied together. This is done by looking for a number that is coprime to m and also has a unique factorization in the set. Once this is found, it is shown that a is also coprime to m.
  • #1
RossH
75
0

Homework Statement


Let b1 through b_phi(m) be integers between 1 and m that are coprime to m. Let B be the product of these integers. Show that B must be congruent to 1 or -1 (mod m)

Homework Equations


None.

The Attempt at a Solution


Well, I know that the quantity B appears during the proof of Euler's formula. That is, that a^phi(m) is congruent to 1 (mod m). So I probably have to work from there somehow. I have looked at Wilson's theorem, Euler's theorem, and Fermat's little Theorem. I'm not really sure where to go from here.
 
Physics news on Phys.org
  • #2
Can't you apply a proof which is similar to the proof of Wilson's theorem?
 
  • #3
micromass said:
Can't you apply a proof which is similar to the proof of Wilson's theorem?

There is no requirement that m be a prime number. That's where I'm confused.
 
  • #4
Allright, can you write the proof to Wilson's theorem here?? Then we can see if the proof is adaptable or not... (in fact: this theorem is a generalization of Wilson's theorem for non-primes, so I suspect that an analogous proof should do)
 
  • #5
micromass said:
Allright, can you write the proof to Wilson's theorem here?? Then we can see if the proof is adaptable or not... (in fact: this theorem is a generalization of Wilson's theorem for non-primes, so I suspect that an analogous proof should do)

Okay, this is how I understand the proof:

To be proved: n>1 is prime iff (n-1)! is congruent to -1 (mod n)
This must be true for 2.
For all integers n>2 in m there exists b in m such that ab is congruent to 1 (mod n).
This b is unique (mod n) [I'm not sure why] and because n is prime, a is congruent to b iff a is 1 or n-1.

So it seems to me that this means that the numbers can be grouped into pairs, where each one will have a pair (b). a*b will always be congruent to 1 based on the number of pairs because n must be odd. No a will have the same pair so this modulus can be raised to an even power, to get 1 [I'm not quite sure why this works].

At least, this is my cursory understanding of the proof.
 
  • #6
Good, now we're going to try to adapt this proof so that it works in this case.

Take [tex]b_1,...,b_{\phi(m)}[/tex] the integers coprime to m. Our goal is to group them in pairs so that they cancel out.

Try to show the following: if b is coprime to m, then there is a unique a such that ab=1 (mod m). Furthermore, a is also coprime to m.
 

1. What is the definition of a product of co primes congruent to 1 (mod m)?

A product of co primes congruent to 1 (mod m) is the result of multiplying two numbers that are relatively prime to each other and have a remainder of 1 when divided by a given integer m.

2. How is the product of co primes congruent to 1 (mod m) useful in number theory?

The product of co primes congruent to 1 (mod m) is useful in number theory because it can help in simplifying equations and identifying patterns in the behavior of numbers. It is also used in the Chinese Remainder Theorem, which is a fundamental theorem in number theory.

3. What is the notation used for expressing the product of co primes congruent to 1 (mod m)?

The product of co primes congruent to 1 (mod m) is often denoted as φ(m), where φ is the Euler's totient function. This function counts the number of positive integers less than or equal to m that are relatively prime to m.

4. Can the product of co primes congruent to 1 (mod m) be used to find the inverse of a number mod m?

Yes, the product of co primes congruent to 1 (mod m) can be used to find the inverse of a number a mod m. The inverse of a is given by aφ(m)-1 (mod m).

5. How can we calculate the product of co primes congruent to 1 (mod m)?

To calculate the product of co primes congruent to 1 (mod m), we can use the formula φ(m) = m(1-1/p1)(1-1/p2)...(1-1/pn), where p1, p2, ..., pn are the prime factors of m. We can also use a table of values or a computer program to calculate the product.

Similar threads

  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
929
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top