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
0 votes
0 answers
25 views

Reference request for a fact about a supremum of congruences

Does anyone know a reference for the following fact about a supremum of congruences? Let $A$ be an algebra, $B$ be a subalgebra of $A$, and $\theta$ and $\theta'$ be congruences of $A$. If $B$ is a ...
user avatar
  • 1,054
0 votes
0 answers
18 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{...
user avatar
1 vote
1 answer
46 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)$?
user avatar
  • 1,188
2 votes
1 answer
58 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. ...
user avatar
2 votes
1 answer
67 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 ...
user avatar
1 vote
1 answer
56 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 ...
user avatar
0 votes
1 answer
47 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 ...
user avatar
-2 votes
1 answer
259 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 ...
user avatar
-1 votes
1 answer
81 views

What is a discrete congruence? [closed]

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. ...
user avatar
2 votes
1 answer
103 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 ...
user avatar
  • 749
0 votes
2 answers
101 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 ...
user avatar
0 votes
1 answer
52 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 ...
user avatar
0 votes
2 answers
38 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-...
user avatar
1 vote
1 answer
48 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 ...
user avatar
  • 4,395
0 votes
1 answer
104 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 ...
user avatar
  • 4,395
1 vote
2 answers
179 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 ...
user avatar
  • 4,395
1 vote
1 answer
34 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 ...
user avatar
  • 600
1 vote
1 answer
44 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$ , $...
user avatar
  • 600
1 vote
1 answer
91 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} \...
user avatar
  • 909
1 vote
0 answers
72 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)^{\...
user avatar
0 votes
1 answer
42 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 ...
user avatar
  • 91
1 vote
1 answer
674 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
300 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
1 vote
2 answers
49 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 ...
user avatar
  • 2,055
0 votes
1 answer
60 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 \...
user avatar
4 votes
1 answer
133 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 ...
user avatar
  • 16.3k
1 vote
1 answer
102 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 ...
user avatar
0 votes
0 answers
24 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$. ...
user avatar
3 votes
1 answer
41 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 ...
user avatar
  • 5,732
0 votes
1 answer
88 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 ...
user avatar
1 vote
2 answers
121 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 ...
user avatar
  • 118
0 votes
0 answers
108 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 ...
user avatar
3 votes
1 answer
48 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$ ...
user avatar
1 vote
0 answers
48 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 ...
user avatar
  • 533
1 vote
0 answers
36 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 ...
user avatar
  • 533
1 vote
2 answers
132 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 ...
user avatar
3 votes
3 answers
154 views

$(\forall n \in \mathbb{Z}):n^{3} \equiv n$ (mod $6$) [duplicate]

[This is not a duplicate, since I am seeking for an alternative proof for this problem] This is a problem from Proofs and Fundamentals, by Ethan D. Bloch. Show that, for all $n \in \mathbb{Z}$, $n^{3}...
user avatar
  • 3,318
4 votes
1 answer
345 views

To prove that an operation is well-defined in modular arithmetic

I started to study the relation of congruence modulo n and a big important question came to me. In the book Poofs and Fundamentals, by Ethan D. Bloch, we have the definition: Definition: Let $n \in \...
user avatar
  • 3,318
3 votes
2 answers
196 views

Find the remainder $1690^{2608} + 2608^{1690}$ when divided by 7?

Find the remainder $1690^{2608} + 2608^{1690}$ when divided by 7? My approach:- $1690 \equiv 3(\bmod 7)$ $1690^{2} \equiv 2(\bmod 7)$ $1690^{3} \equiv-1 \quad(\mathrm{mod} 7)$[ quite easy to ...
user avatar
0 votes
2 answers
38 views

Modulus and Congruences, odd example.

Hey guys I am reading a math book and I got a bit confused on the congruence chapter. I have just seen that $a \pmod n$ = remainder of n|a. However as an example of " a (mod n) = remainder ",...
user avatar
  • 211
2 votes
1 answer
55 views

Showing that there's no solution to the congruence $x^{2}+3y^{2}\equiv2\mod3$

I was given the following question: Let $x,y\in \mathbb{Z}$, show that the congruence $x^{2}+3y^{2}\equiv2\mod3$ has no solution. Here's my attempt so far: $x^{2}+3y^{2}\equiv2\mod3$ $\Rightarrow x^{2}...
user avatar
  • 321
0 votes
1 answer
122 views

Looking for help with reasoning about a function defined on congruence relations

Let: $T_{p,r}(n,x)$ be the count of integer $i$ such that: $p$ is an odd prime $n,r<p,x$ are integers $n - x \le i < n$ $i \equiv r \pmod {p}$ for all prime $q > 2$ where $i \equiv r \pmod {...
user avatar
2 votes
0 answers
148 views

How To Solve The Congruence $n\equiv1\pmod{\tau(n)}$

This problem raised in my mind while solving an elementary number theory problem. Problem statement: For $n\in \mathbb{N}$ let $\tau(n)$ notes the number of positive divisors of $n$ including $1$ and $...
user avatar
0 votes
1 answer
29 views

Can anyone explain how to solve this kind of questions?

Here's the question: Find an appropriate solution for x. 𝑥 ≡ 2 (𝑚𝑜𝑑 3) 𝑥 ≡ 2 (𝑚𝑜𝑑 5) 𝑥 ≡ 5 (𝑚𝑜𝑑 7) 𝑥 ≡ 7 (𝑚𝑜𝑑 8) I saw some examples like this question...but I still don't ...
user avatar
0 votes
0 answers
46 views

Different versions of $(\mathbb{Z}^{*}_{2^k}, \cdot)$

I had to prove two statments, which I was supposed to use to prove two other ones: For $k \geq 3, \:$ $\:5^{2^{k-3}} \equiv 1 \: \mod 2^{k-1}$, but $5^{2^{k-3}} \not\equiv 1 \mod 2^k$ For $k \geq 3, \...
user avatar
0 votes
1 answer
46 views

Congruence Implication with $2^k$

For $k \geq 3$ I have to show the following implication: $$ (-1)^i5^j \equiv (-1)^m5^n \mod2^k \Rightarrow (-1)^i \equiv (-1)^m \mod4$$ I have tried a few things but I couldn´t solve it, I would ...
user avatar
-1 votes
1 answer
38 views

Why does this equality hold when solving linear congruence? [duplicate]

I am quite confused about specific equality that is used when solving linear congruences. In the example provided, it is the jump from the second to last equation to the final equation. I cannot seem ...
user avatar
0 votes
2 answers
109 views

Why Are Congruence Relations Written as $”a\equiv b \pmod m”$ [duplicate]

Why when writing a congruence relation, do we have to add $\pmod{m}$ at the end. I understand it's notation, but $b$ does not have to be equal to $a\bmod b$ if I understand correctly. The definition ...
user avatar
7 votes
0 answers
113 views

Should we teach congruences from the start rather than normal subgroups in group theory? [closed]

Many students have difficulty initially with the idea of a quotient group, and why a normal subgroup is defined as it is. I think this is potentially made worse by the slightly obscure logic of the ...
user avatar
0 votes
2 answers
83 views

Let $K = \mathbb F_p[x]/f(x)$. Find all roots of $f(t)$ in $K$. ($p$ is prime and $f(x)$ is irreducible)

This question confuses me. I'm not sure how to go about finding the roots of the polynomial in the field extension K. Just to clarify I have an example if it helps but I just need to understand. Let $...
user avatar
  • 25

1
2 3 4 5