MHB System of congruences with no solution

  • Thread starter Thread starter vincentvance
  • Start date Start date
  • Tags Tags
    System
AI Thread Summary
The discussion centers on proving that the system of congruences x ≡ 5 (mod 6) and x ≡ 7 (mod 15) has no solution. To understand this, it's essential to analyze the implications of each equation under modulo 3, as both 6 and 15 are multiples of 3. The first equation leads to x ≡ 2 (mod 3), while the second results in x ≡ 1 (mod 3), creating a contradiction. The clarification provided explains that if x ≡ 5 (mod 6), it can be expressed as a multiple of 3 plus 2, confirming the inconsistency. This analysis highlights the lack of a common solution for the system.
vincentvance
Messages
8
Reaction score
0
Hello,

I am trying to prove that the system

x ≡ 5 (mod 6)
x ≡ 7 (mod 15)

has no solution. This example is done in my textbook and they say one should first assume that there is a solution x, and that when taking classes mod 6 the second equation implies that 2x ≡ 2 (mod 6). After this the example continues and I can follow the remaining steps, but this particular part I don't understand. What does it mean to "take classes mod 6" and why does the second equation imply that 2x ≡ 2 (mod 6)?

Any help is greatly appreciated.
 
Physics news on Phys.org
vincentvance said:
Hello,

I am trying to prove that the system

x ≡ 5 (mod 6)
x ≡ 7 (mod 15)

has no solution. This example is done in my textbook and they say one should first assume that there is a solution x, and that when taking classes mod 6 the second equation implies that 2x ≡ 2 (mod 6). After this the example continues and I can follow the remaining steps, but this particular part I don't understand. What does it mean to "take classes mod 6" and why does the second equation imply that 2x ≡ 2 (mod 6)?

Any help is greatly appreciated.
You might find it easiest to understand this by working mod 3, using the fact that 6 and 15 are both multiples of 3. In fact, if $x \equiv 5\pmod6$ then $x\equiv2\pmod3$. But if $x\equiv7\pmod{15}$ then $x\equiv1\pmod3.$
 
Opalg said:
You might find it easiest to understand this by working mod 3, using the fact that 6 and 15 are both multiples of 3. In fact, if $x \equiv 5\pmod6$ then $x\equiv2\pmod3$. But if $x\equiv7\pmod{15}$ then $x\equiv1\pmod3.$

I feel like such an idiot, but I don't understand why for example if x ≡ 5 (mod 6) then x ≡ 2 (mod 3).
 
vincentvance said:
I don't understand why for example if x ≡ 5 (mod 6) then x ≡ 2 (mod 3).
Think of it from the basic definition. If x ≡ 5 (mod 6), it means that $x$ is a multiple of 6, plus 5. Say $x = 6k+5$, for some integer $k$. You can write that as $x = 3(2k+1) + 2$. In other words, $x$ is a multiple of 3, plus 2. That is the same as saying x ≡ 2 (mod 3).
 
Opalg said:
Think of it from the basic definition. If x ≡ 5 (mod 6), it means that $x$ is a multiple of 6, plus 5. Say $x = 6k+5$, for some integer $k$. You can write that as $x = 3(2k+1) + 2$. In other words, $x$ is a multiple of 3, plus 2. That is the same as saying x ≡ 2 (mod 3).

Ah. Of course, now it makes sense. Thank you so much!
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top