Questions tagged [congruence-relations]

For questions about general congruence relations, i.e. equivalence relations on an algebraic structure that are compatible with the structure. Please DO NOT use this for questions about integer modular arithmetic.

Filter by
Sorted by
Tagged with
2 votes
1 answer
34 views

Congruence lattice of a semiring

A famous result of Funayama and Nakayama states that the congruence lattice of any lattice is a distributive lattice [1]. Also, it can be proved that the lattice is a frame/ complete Heyting algebra 2....
MathCosmo's user avatar
  • 926
3 votes
1 answer
104 views

Identifying group of units of monoid to a point

Let $S$ be a monoid. Let $\mathfrak{g}(S)$ be the group of units of $S$, and denote by $S/A$ the quotient $S/\sim_A$ where $\sim_A$ is the smallest congruence such that $a\sim_A a'$ for all $a, a'\in ...
Jakobian's user avatar
  • 10.3k
1 vote
1 answer
98 views

Defining Addition/Multiplication on $\Bbb Z_3$

On $\Bbb Z_3$, we typically define addition and multiplication as follows: $$[a]+[b]=[a+b]$$ $$ [a]\cdot[b]=[a\cdot b]$$ Consider defining addition as $[a]+[b]=[0]$ for all $a,b\in \Bbb Z$. This ...
monkey king's user avatar
1 vote
1 answer
45 views

Is there alternative symbol for congruence classes?

I saw on youtube a talk about the congruence classes. For example, the congruence classes modul0 4 are written as followings. $[0]_4 = \{0, 4, 8, 12, \dots \} $ $[1]_4 = \{1, 5, 9, 13, \dots \} $ $[2]...
Jerry's user avatar
  • 33
3 votes
1 answer
95 views

Exercise 4, Section 1.5 of Hungerford’s Abstract Algebra

Let $\backsim$ be an equivalence relation on a group $G$ and $N=\{a\in G\mid a\backsim e\}$. Then $\backsim$ is a congruence relation on $G$ if and only if $N$ is a normal subgroup of $G$ and $\...
user264745's user avatar
  • 4,153
3 votes
2 answers
167 views

Exercise 3, Section 1.5 of Hungerford’s Abstract Algebra

Definition: Let $(G,\circ)$ be a group. A congruence relation on $G$ is an equivalence relation $\equiv$ on the elements of $G$ satisfying if $g_1\equiv g_2$ and $h_1\equiv h_2$, then $g_1\circ h_1\...
user264745's user avatar
  • 4,153
3 votes
1 answer
113 views

When does this construction always yield a congruence?

Suppose $\mathcal{M}$ is a commutative monoid and $E$ is any equivalence relation on $\mathcal{M}$. Define $\widehat{E}$ to be the "shift-invariant" part of $E$, that is, $$a\widehat{E}b\...
Noah Schweber's user avatar
1 vote
0 answers
18 views

Linear congruential generator and hyperplanes

Given $x_{n+1}=1229x_n \pmod{2048}$ and $u_n=x_n/2048$, I have to find the number of lines on which the points $(u_n,u_{n+1})$ lie. I know that by Marsaglia's theorem, this will be $(2048\cdot 2)^{1/2}...
Analysis's user avatar
  • 2,450
1 vote
1 answer
72 views

Combinatorial proof of binary partition function $b(n)$ is always even

For all integer $n$, let $b(n)$ be the number of partition of $n$ into power of two. For instance, $b(4)=4$, since \begin{align*} 4 &= 2^2 \\ &= 2^1+2^1 \\ &= 2^1+2^0+2^0 \\ &= 2^0+2^0+...
user avatar
3 votes
1 answer
331 views

Congruence properties of binary partition function

For every positive integer $n$, denote $b(n)$ be the number of binary partition of $n$, i.e., the number of partition of $n$ into power of two, where the power is decreasing. For instance, $b(5)=4$ ...
user avatar
2 votes
1 answer
59 views

Principal congruence of a distributive lattice.

The following problem is taken from Burris and Sankappanavar's A Course in Universal Algebra (11, pg 42). Suppose $L$ is a distributive lattice and $a,b,c,d\in L$. Then $\langle a, b\rangle\in\Theta(c,...
Mashiath Khan's user avatar
3 votes
1 answer
73 views

Every equivalence relation $x \equiv y$ compatible with the structure of a module $E$ is of the form $y-x \in M$ for some submodule $M$ of $E$.

On the end of page 196 of Bourbaki’s Algebra I, it says: Let $E$ be an $A$-module. Every equivalence relation $x \equiv y$ compatible with the structure of a module $E$ is of the form $y - x \in M$ ...
Hoji's user avatar
  • 574
2 votes
1 answer
72 views

Quotients of preordered groups

A preordered group is a group along with a preorder that makes addition monotone. As it is well known, a congruence in a group is equivalent to a normal subgroup. Everyone knows that a preorder on a ...
Subscribe for more Minecraft's user avatar
1 vote
1 answer
41 views

Are congruence classes of a monoid of equal size?

In group theory, cosets of a normal subgroup are disjoint and all of the same size. For monoids, the analogy are congruence classes which partition the monoid. Are they also of equal size? By the way, ...
alagris's user avatar
  • 193
0 votes
0 answers
66 views

What does the author mean here by the congruence relation generated by -?

I am reading up on Wheel Theory using the notes found at https://www2.math.su.se/reports/2001/11/2001-11.pdf. There really doesn't seem to be many online notes for this topic. It starts by motivating ...
Riemann'sPointyNose's user avatar
0 votes
0 answers
30 views

how to prove for $m \in \mathbb{Z}$ that m.(\bar{a}+\bar{b})=m.\bar{a}+m.\bar{b}? [duplicate]

I'd like to know why $m.(\bar{a}+\bar{b})=m.\bar{a}+m.\bar{b}$, $m \in \mathbb{Z}$, where $\bar{a}=\{x \in \mathbb{Z}:x=a+nq\}$ . , + are the congruence operations of multiplication and sum. and $\bar{...
Davi Américo's user avatar
1 vote
1 answer
105 views

How to find new number congruent to another one with respect to some given congruences? [duplicate]

If $a \equiv 4 (mod 13)$ and $b \equiv 9 (mod 13)$, then how can we find $0 \leq c \leq 12$ such that $c \equiv 9a (mod 13)$ and $ c \equiv 2a+3b (mod 13)$?
Nil's user avatar
  • 1,316
2 votes
1 answer
96 views

I don't understand a part of the solution involving Chinese remainder theorem

This is the problem statement: Prove there are infinitely many natural numbers $x = \overline{a_{k}a_{k-1}...a_{2}a_{1}}$, (where $a_{k} \neq 0$) such that $x$ and $x^2$ have the same k-digit ending. ...
Marko Sladojevic's user avatar
2 votes
1 answer
239 views

Incongruent Solutions of a Quadratic congruence

I have been reading up on finding incongruent solutions of quadratic congruences and have stumbled upon an answer to a question asked here. The answer I am confused about is the following: "if ...
Pauliene's user avatar
2 votes
1 answer
103 views

How to prove these algebras are subdirectly irreducible, using the claim about their congruence relations? Am I proceeding correctly?

I am solving an exercise from my class and my task is to prove that two algebras descried below are subdirectly irreducible. I have described the algebras and their non-trivial congruence relations ...
Tereza Tizkova's user avatar
0 votes
1 answer
103 views

How do you describe congruence classes in general?

I have studied equivalence and congruence classes before, know the definitions, but I am still unable to work with congruences. Could you please explain, how do the congruence classes look? For ...
Tereza Tizkova's user avatar
-2 votes
1 answer
332 views

Prove Use Fermat Little Theorem gcd(k, 2^n + 3^n + 6^n - 11) = 1

I was asked to prove : Let k be a positive integer. Prove that gcd(k, 2^n + 3^n + 6^n - 11) = 1 for every integer n >= 2 if and only if k = 1. I tried to use FlT, 2^p congruent to 2, 3^p congruent ...
Milliken Farmer's user avatar
0 votes
1 answer
207 views

What is a discrete congruence?

I know a congruence (or congruence relation) is an equivalence relation on an algebraic structure, compatible with the operation on the structure. I am also familiar with equivalent definitions. ...
Tereza Tizkova's user avatar
2 votes
1 answer
619 views

System of three linear congruences with three variables

I have the following system $$ \left\{ \begin{array}{c} 5x+20y+11z \equiv 13 \pmod{34}\\ 16x+9y + 13z \equiv 24\pmod{34} \\ 14x+15y+15z \equiv 10\pmod{34} \end{array} \right. $$ I'm still fairly ...
john doe's user avatar
  • 893
1 vote
2 answers
130 views

Draw lattice of all subuniverses or congruences

I am solving this exercise: Draw lattices of all subuniverses and of all congruences of $(\mathbb{N}, \star)$, where $x \star y$ is defined as $\max(x, y) + 1$ and $\mathbb{N}$ is the natural numbers ...
Tereza Tizkova's user avatar
0 votes
1 answer
160 views

What is the interpretation of congruence relations?

I am studying universal algebra and read An Invitation to General Algebra and Universal Constructions by Bergman. This is a definition from the book, about congruences. My question is, what is a ...
Tereza Tizkova's user avatar
0 votes
2 answers
56 views

Why is addition not commutative under PM's notion of relation number?

Quoting Bertrand Russell's "The Principles of Mathematics" p468 §299: It is worth while to repeat the definitions of general notions involved in terms of what may be called relation-...
James Bowery's user avatar
1 vote
1 answer
228 views

Modulo in modulo operation vs in congruence relations.

Is the "modulo" in modulo operation and in congruence relations, the same? I don't know how the definitions go but I'm going to try to define modulo operation in my own words. Modulo ...
William's user avatar
  • 4,893
0 votes
1 answer
331 views

How to choose a modulus while solving problems in Number Theory?

I'm a beginner and I've only recently picked up "congruence relations". I recently asked a question about intuition for congruence relations, but I figured that maybe if I just do some ...
William's user avatar
  • 4,893
2 votes
2 answers
371 views

Intuition and motivation for congruence relations modulo $n$?

I'm trying to learn a bit of Number Theory. And while I understand the definition of congruence relations modulo $n$ and that they are an equivalence relations, I fail to see the motivation for it. So ...
William's user avatar
  • 4,893
2 votes
1 answer
50 views

Does a congruence relation on a complete lattice automatically also preserve the completeness property?

Suppose that $(X,\wedge,\vee)$ is a complete lattice and that $\equiv$ is a congruence relation on $(X,\wedge,\vee)$, i.e, for all $x_1$, $x_2$ , $y_1$ and $y_2$ in $X$ $x_1\equiv y_1$ and $x_2\equiv ...
Bart's user avatar
  • 1,093
2 votes
1 answer
99 views

What is the definition of a congruence relation on an order-theoretic lattice?

A congruence relation on a (as an algebraic structure defined) lattice $(X,\wedge,\vee)$ is an equivalence relation $\equiv$ on $X$ that preserves the lattice structure, i.e, for all $x_1$, $x_2$ , $...
Bart's user avatar
  • 1,093
1 vote
1 answer
110 views

$\prod_{i=1}^{n} (3 +\frac{1}{a_i})$ cannot be a power of 2 if $a_i \equiv \pm 1 \pmod 6$

I have encountered this problem and I can't solve it. If $a_i \equiv 1 \pmod 6$ or $a_i \equiv -1 \pmod \ 6$ and $a_i \ne \pm 1$, for every $i \in \{1, 2, .., n\}$, then prove that $$\prod_{i=1}^{n} \...
andu eu's user avatar
  • 941
1 vote
0 answers
116 views

Congruence relation on a category generated from a collection of relations on each hom-set?

Using the definition of a "congruence relation" on a category (as defined here), I was wondering if there is a notion of the congruence relation $$ \{E_{x,y}\subset \mathrm{Hom}_C(x,y)^{\...
I.A.S. Tambe's user avatar
  • 2,431
0 votes
1 answer
100 views

How to show that the set of complete lattice congruences of an complete lattice is again complete lattice?

Thank you for your help. I am now trying to understand that the set of complete lattice congruences of a complete lattice is again complete lattice. Let $\mathcal{L}$ be a complete lattice. An ...
sola's user avatar
  • 121
6 votes
1 answer
2k views

What is the remainder when $6^{273} + 8^{273}$ is divided by $49$?

What is the remainder when $6^{273} + 8^{273}$ is divided by $49$? I tried this question through two methods and both are giving different answers so I wanted to know which is the correct one, and ...
user avatar
2 votes
1 answer
872 views

Prove that $a + 2b \equiv 0 \bmod 3$ is an equivalence relation [duplicate]

Would this proof work to show that $R$ ={(x, y) ∈ ℤ2: x + 2y ≡3 0} is an equivalence relation? Reflexive: Let x ∈ ℤ. x + 2x= 3x, and 3x ≡ 0 mod 3 since 3 divides 3x with remainder 0. Symmetric: Let x,...
user avatar
0 votes
2 answers
80 views

The only equivalence relations on $\mathbb{Z}$ that are compatible with the ring operations are congruences modulo $n$ for $n \in \mathbb{Z}$

It's (probably) a fairly basic result that the only equivalence relations on $\mathbb{Z}$ that are compatible with the ring operations are congruences modulo $n$ for $n \in \mathbb{Z}$... as it's ...
the gods from engineering's user avatar
0 votes
1 answer
193 views

Understanding the Generalised Chinese Remainder Theorem

The generalised version of the theorem I'm working with is: If $R$ is a commutative Ring with unity and $I_1,\ldots , I_n$ ideals of $R$, then the map $$\phi: R \to \frac{R}{I_1}\times\ldots\times \...
Silver Pine's user avatar
4 votes
1 answer
199 views

Do quotient inverse semigroups exist?

A congruence on a semigroup $S$ is an equivalence relation $\sigma\subseteq S\times S$ that respect to the multiplication. In other words $$(a,b), (c,d)\in\sigma \implies (ac, bd)\in\sigma. $$ Given a ...
Bumblebee's user avatar
  • 18.3k
2 votes
1 answer
324 views

Congruence relation of an Algebra

Let $2=\{0,1\}$, $+$ denote addition modulo $2$, $g\left(x\right)=x+1$. Consider the following Algebra $A=\langle 2,+,g\rangle$. I want to calculate congruence relation on $A\times A$. Can someone ...
sushil soni's user avatar
0 votes
0 answers
67 views

What differs a ring ideal from a congruence class in the integers?

I know the following definitions: Congruence: $a \equiv b \pmod{n}$ if $n \mid a-b$ A subring $I$ of a ring $R$ is an ideal if whenever $r \in R$ and $a \in I$, then $ar \in I$ and $ra \in I$. ...
user9750060's user avatar
3 votes
1 answer
57 views

Varieties in which congruences are characterized by subalgebras

For some varieties $V$, for any algebra $\mathbb{A}\in V$, there exists a lattice isomorphism $f:\text{Con}(\mathbb{A})\to \mathbb{B}$ where $\mathbb{B}\leq \text{Sub}(\mathbb{A})$ between the lattice ...
Jakobian's user avatar
  • 10.3k
1 vote
1 answer
138 views

Universal Algebra: an application of a Maltsev's algorithm to characterize congruences

In "Universal Algebra: Foundamentals and Selected Topics (pg. 107)" of Clifford Bergman the following Maltsev's theorem is intoduced for constructing congruences. Let $\textbf{A}$ be an ...
Giovanni Barbarani's user avatar
2 votes
2 answers
193 views

The only congruence is the identity congruence [From Algebraic Methods in Philosophical Logic, Dunn and Hardegree]

In the book "Algebraic Methods in Philosophical Logic" by Dunn and Hardegree I was very much confused by the remark 2.6.7 on page 22. In this book a relational structure $\mathbf{A}$ is ...
Mentastin's user avatar
  • 148
0 votes
0 answers
116 views

Let R and S be binary relations on a set A. Solve for each case: If R and S are i) reflexive, ii) symmetric, iii) transitive, what would R∪S be? [duplicate]

I had a similar question just now and it peaked my interest on binary relations. Solving i) "Assuming R and S are reflexive so: Let x ∈ A. Then (x, x) ∈ R and (x, x) ∈ S (reflexive property of R ...
tonysoprano555's user avatar
3 votes
1 answer
60 views

Qutoient monoid of kernel pair of monoid homomorphism between multiplicative naturals to additive naturals (sum of prime numbers).

Let $M = \Bbb{N}^{\times}$ and $N = (\Bbb{N}\setminus \{1\} \cup \{0\})^+$ be the multiplicative, and respectively, the additive naturals and let $\varphi : M \to N$ be defined by taking $1$ to $0$ ...
Daniel Donnelly's user avatar
1 vote
0 answers
270 views

Question On Solutions for a Specific Congruence $ax \equiv 1 \pmod p$ when $p$ is prime and $p \not\mid a$

I have been working through exercises within a book on polynomials. Part (f.) of a particular exercise asks the following : Show that, if $p$ is a prime, and $a$ is not a multiple of $p$, then there ...
scipio's user avatar
  • 595
1 vote
0 answers
39 views

Question Concerning Solutions of a Congruence that is Unique Modulo m [duplicate]

I have been working through exercises in a book on polynomials. There is a section in the first chapter on some basic number theory. I am having trouble completing one of the exercises. Part (e.) of ...
scipio's user avatar
  • 595
1 vote
2 answers
198 views

Diophantine Equation with Square Root

I want to resolve the diophantine equation: $\sqrt{x^2+5x+12} ≡ x-2\pmod 5$ I have thought 2 ways: 1. $(\sqrt{x^2+5x+12})^2 ≡ (x-2)^2\pmod 5$ $ x^2+5x+12 ≡ x^2 -4x+4\pmod 5$ $ 9x+8 ≡ 0\pmod 5$ $ 4x+3 ...
Javier Álvarez's user avatar

1
2 3 4 5