Number of solutions (equivalence classes) of congruence

  • Thread starter fleazo
  • Start date
  • Tags
    Classes
In summary, there are three equivalence classes for the congruence 3x+11=20(mod12) which are represented by [3], [7], and [11]. This can be determined by finding the values in the set {...,-5,-1,3,7,11,...} that fall within the range [0,11]. The remaining values will differ by a multiple of 12. This can be thought of as finding the "generators" of a cyclic group.
  • #1
fleazo
81
0

Homework Statement



How many solutions (equivalence classes) are there for the congruence 3x+11=20(mod12)

Homework Equations



a=b(modn) then for all c,
a+c=b+c(modn)
ac=bc(modn)

ab=ac(modn) then
b=c(modn) (if gcd(a,n)=1)
b=c(mod(n/d)) if gcd(a,n)=d > 1

The Attempt at a Solution



3x+11=20(mod12)
3x=9(mod12)
x=3(mod4) (because gcd(12,3)=4>1)

so solutions are x in the following set::

{...,-5,-1,3,7,11,...} (we can get these from the equation f(x)=4x+3)

The question is, how many equivalence classes are here? I can just test out [0],[1],[2],...,[11] hand by hand and find that [3], [7], and [11] represent all the possible solutions. But my question is, what's a faster way to do this? What theorem can I use that will tell me which equivalence classes are equal? (my initial thought was it would have to do with n and a being relatively prime, but 3 and 12 are not relatively prime and yet [3] is one of the equivalence classes so clearly I'm wrong there) Is this something like finding the "generators" of a cyclic group?
 
Physics news on Phys.org
  • #2
Mmm. Two equivalence classes [a] and are equal mod 12 if a-b is a multiple of 12. So if you have {...,-5,-1,3,7,11,...}, you just have to pick the ones that lie in range [0,11]. All of rest will differ from them by a multiple of 12. Or am I not getting what you are asking?
 

What is the definition of congruence?

Congruence is a mathematical concept that refers to the relationship between two numbers that have the same remainder when divided by a given number. In other words, two numbers are congruent if they have the same "shape" or pattern when divided by a certain number.

What is the difference between congruence and equality?

Congruence and equality are two different mathematical concepts. While equality means that two numbers are exactly the same, congruence means that two numbers have the same remainder when divided by a certain number. In other words, congruence is a more specific form of equality.

How many possible solutions or equivalence classes are there for congruence?

The number of solutions or equivalence classes for congruence depends on the given number or modulus. For example, if the modulus is 5, there will be 5 possible equivalence classes (0, 1, 2, 3, and 4). In general, the number of solutions will always be equal to the modulus.

Can two numbers be congruent to more than one modulus?

No, two numbers can only be congruent to one modulus at a time. This is because the relationship of congruence is defined by the modulus. If two numbers have the same remainder when divided by one modulus, they may not have the same remainder when divided by another modulus.

How is congruence used in real-life situations?

Congruence is used in various fields such as engineering, computer science, and cryptography. In engineering, it is used for measuring angles and determining similar shapes. In computer science, it is used for data encryption and error correction. In cryptography, it is used for creating secure codes and ciphers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
717
  • Calculus and Beyond Homework Help
Replies
5
Views
977
  • Precalculus Mathematics Homework Help
Replies
5
Views
853
  • Calculus and Beyond Homework Help
Replies
2
Views
977
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
865
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
777
Back
Top