Question related to congruence class equations

  • Thread starter General_Sax
  • Start date
  • Tags
    Class
In summary, the problem states that for an integer a = 0 and a natural number n, if the greatest common divisor of a and n is 1, then there exists an integer b such that a*b is congruent to 0 modulo n. The solution involves finding a value for b that shares a common divisor with both a and n. The writer suggests trying b = a*k or b = a+k, where k is an integer, but is unsure how to express this mathematically. They are seeking help with writing a formal proof for this problem.
  • #1
General_Sax
446
0

Homework Statement



3) Let a be an integer = 0 and 6 n a natural number. Show that if gcd(a, n) = 1 then 6
there exists b ∈ Z, such that [a] · = [0] and = [0] in 6 Z/Zn


Homework Equations





The Attempt at a Solution



Ok, so I'm still trying to digest the question and so far I'm going with the fact that if b is a integer multiple of a, ie, b := KONSTANT*a then it should still share a common divisor with both 'n' and 'a'. However, I'm also thinking that b could be --- b := KONSTANT + a. Now, I'm not too sure about the last part, but I think as long as the KONSTANT has a common divisor with [a] and n, then it should still work out. Any comments on my ideas or help in expressing them mathematically?

I'm just not too sure on how to write this up, as I'm not very experienced with 'proofs'.
 
Physics news on Phys.org
  • #2
that supposed to read a!= 0 and b != 0 ... srry just copy and pasted.
 

FAQ: Question related to congruence class equations

What is a congruence class equation?

A congruence class equation is an equation that compares two numbers or expressions using the concept of congruence. Congruence means that the two numbers or expressions have the same remainder when divided by a certain number, called the modulus.

How do you solve a congruence class equation?

To solve a congruence class equation, you need to first determine the modulus. Then, you can use basic algebraic operations such as addition, subtraction, multiplication, and division to manipulate the equation and find the solutions.

What is the Chinese Remainder Theorem and how does it relate to congruence class equations?

The Chinese Remainder Theorem is a mathematical theorem that states that if two numbers are relatively prime, then any system of congruence equations can be solved by finding the solutions to each individual equation and combining them using the Chinese Remainder Theorem formula. This theorem is often used in solving congruence class equations.

Can congruence class equations have more than one solution?

Yes, congruence class equations can have multiple solutions. The number of solutions will depend on the modulus and the specific equation. In some cases, there may be infinitely many solutions.

How are congruence class equations used in real-life applications?

Congruence class equations are used in various fields such as cryptography, computer science, and engineering. They are particularly useful in dealing with remainders and modular arithmetic, which have practical applications in data encryption, error detection, and computer algorithms.

Similar threads

Chinese Remainder theorem for 2 congruences
Replies
2
Views
1K
Using class equation to show that intersection is nontrivial
Replies
1
Views
1K
Number of solutions (equivalence classes) of congruence
Replies
1
Views
2K
How can I find 544 mod 3 using congruence
Replies
27
Views
2K
Solving simultaneous congruences
Replies
6
Views
1K
Elements of an Equivalence Class
Replies
8
Views
2K
Order of a^m when gcd(m,n) = 1
Replies
2
Views
2K
Constructing Cones as Orbifolds: Fundamental Domain for an Identification
Replies
4
Views
920
Proving Normality of [0] in Z/3Z Quotient Group
Replies
4
Views
4K
Number Theory. If d=gcd(a,b,c) then d is a linear combination of a,b, and c
Replies
1
Views
3K

Hot Threads

Recent Insights

Back
Top