Questions tagged [congruence-relations]

For questions about congruence relations, equivalence relations on an algebraic structure that are compatible with the structure.

Filter by
Sorted by
Tagged with
-1
votes
3answers
63 views

$437$ divides $16^{99} -1$. Help to finish it.

I am doing an exercise and find a question which I can't answer. The exercise asks to show that $16^{99}\equiv 1 \pmod{437}$. Since $\gcd(16,437)=1$, Euler's theorem says $$ 16^{\varphi (437)}\equiv 1\...
0
votes
1answer
33 views

Solving congruence problem [duplicate]

Let $p$ be a prime number of the form $4n+1$, and let $n$ be a natural number. Show that congruence $x^2\cong-1 \mod p$ is solvable. I tried solving by simplifying $\cong$ sing i.e. $x^2 + 1 = p.m$ or ...
0
votes
1answer
69 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 ...
1
vote
2answers
87 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 ...
0
votes
0answers
12 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 ...
3
votes
1answer
29 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$ ...
1
vote
0answers
33 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 ...
1
vote
0answers
35 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 ...
1
vote
2answers
70 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 ...
3
votes
3answers
82 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}...
4
votes
1answer
73 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 \...
0
votes
0answers
21 views

Equivalence of Similarity & Congruences in Euclidean Geomtery

Let us define the following: SAS (Side-Angle-Side): If two pairs of sides of two triangles are equal in length, and the included angles are equal in measurement, then the triangles are congruent. SSS ...
3
votes
2answers
90 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 ...
0
votes
2answers
33 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 ",...
2
votes
1answer
48 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}...
1
vote
0answers
71 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 {...
-1
votes
1answer
25 views

Question on solutions for distinct congruence classes b mod n [duplicate]

For how many distinct congruence classes $[b]$ mod $631$ will there be integer solutions $x$ to the congruence $$x^2\equiv b\,(mod\,631)$$
2
votes
1answer
134 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 $...
0
votes
1answer
27 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 ...
0
votes
0answers
37 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, \...
0
votes
1answer
41 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 ...
-1
votes
1answer
26 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 ...
0
votes
2answers
50 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 ...
6
votes
0answers
78 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 ...
0
votes
2answers
53 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 $...
0
votes
1answer
29 views

Principal congruences defined by terms

I'm having trouble understanding an exercise of the book "A course in Universal Algebra". Show that for any algebra $A$ and $a, b \in A$, $Θ(a,b) = t^*(s(\{(p(a,\bar{c}), p(b, \bar{c})): p(x, y_1, ....
5
votes
4answers
63 views

Group congruences: If the operation is preserved, do we get $a\sim b$ $\Rightarrow$ $a^{-1}\sim b^{-1}$?

Let $(G,*)$ be a group. Let $\sim$ be an equivalence relation such that $$(\forall a,a',b,b'\in G)a\sim a', b\sim b' \Rightarrow a*b\sim a'*b'. \tag{*}$$ I.e., the equivalence relation $\sim$ respects ...
0
votes
0answers
20 views

Difference of congruence relations concerning monoid homomorphisms

So there is the congruence relation defined for an "amalgamated sum" of monoid morphisms that is generated by $((a,b),(a',b'))\in (N_1\oplus N_2)\times (N_1\oplus N_2)$ such that there is an element $...
0
votes
2answers
60 views

Is 7($11^{106}$)+290 divisible by 13? [duplicate]

I know I can check this using congruence, which is how I should be approaching this problem. There are so many ways I can go about the problem, but I keep getting stuck on the $11^{106}$ term. To ...
0
votes
1answer
63 views

Prove that if $p$ is prime, then an element of $\mathbb{Z} /p \mathbb{Z}$ has at most two square roots. [duplicate]

We say that $[a]$ is a square root of $[b]$ in $\mathbb{Z}/p\mathbb{Z}$ if $[a]^2= [b]$. Prove that if $p$ is prime, then an element of $\mathbb{Z}/p \mathbb{Z}$ has at most two square roots?
0
votes
0answers
47 views

How can we obtain $\sum_{l=1}^{m}(-1)^{l+1} \binom{m}{l} \equiv 1\pmod{p}$ [duplicate]

How can we obtain $$\sum_{l=1}^{m}(-1)^{l+1} \binom{m}{l} \equiv 1 \pmod{p} $$ Please give me an idea to obtain this.
1
vote
0answers
23 views

Congruence on semigroup [duplicate]

For a commutative semigroup $S$, define the relation $\theta_n^S\ \ (n\geqslant 1)$ by $$a\theta_n^Sb\text{ if and only if } (\forall x\in S^n) xa = xb. $$ (a) Show that $\theta_n^S$ is a congruence ...
0
votes
0answers
54 views

$k-$th root modulo $n$.

Let $p$ be a prime and $b,k\in \mathbb{N}$, if $gcd(b,p)=1$ and $k|p-1$ then $x^k \equiv b \mod{p} $ has exactly $k$ incongruent solution. Is the above statement correct, I feel like I had got a ...
2
votes
1answer
76 views

Integer Factor Congruence

Given an integer $N$, with unknown prime factors $f_1$, $f_2$ ... $f_n$, and given unique integers $k_1$, $k_2$ ... $k_n$, with $\sqrt{N} \geq k_i>2$ for all $i$ such that $$f_1 \equiv 1\pmod {k_1}$...
1
vote
2answers
48 views

$n\bar k=\overline{nk}$ in $Z_m$?

I was reading Algebra of Hungerford, the (sketch of) proof of Theorem 3.6. Definitions : Let $m$ be a positive integer. The equivalence relation '$\equiv$' modulo $m$ partitions $\mathbb Z$ into $m$ ...
0
votes
0answers
25 views

Use Sylvester's theorem to find the number of congruence classes in an $n$ dimensional vector space

Quadratic forms on the $n$-dimensional vector space $𝑉$ over a field $𝐾$ are congruent if one can be obtained from the other by a change of coordinates. Or equivalently, if there exists $P$ such ...
0
votes
0answers
20 views

Number of congruency equivalence classes for symmetric bilinear forms in the complex numbers

Call two quadratic forms on the n-dimensional vector space $V$ over field $K$ congruent if one can be obtained from the other by a change of coordinates. Congruence is an equivalence relation on the ...
1
vote
2answers
126 views

Proving that if gcd(a,n)=gcd(b,n)=1, then ax+by = c (modn) has exactly n different solutions mod n.

I am taking an undergraduate course in basic Number Theory, and I came across this question in my textbook: Show that if $\text{gcd}(a,n)=\text{gcd}(b,n)=1$, then $ax+by\equiv c(\text{ mod }n) $ has ...
0
votes
1answer
28 views

Prove/Disprove that the following relation is a congruence relation

Prove/Disprove that the following relation is a (right-) congruence relation: $w R_3 v \iff$ All characters that occur in the word $w$ and only these occur in the word $v$. Note: A character $x\in\...
0
votes
1answer
54 views

How to solve a non-linear system of modulus equations?

I have the following problem: $$ 2x^2 + 8 \equiv 6 \;(\bmod\;13)$$ $$x \equiv 2 \;(\bmod\;15)$$ I have tried applying the Chinese remainder theorem, but could not figure out how to make it work, as ...
2
votes
2answers
90 views

“Self-congruent” matrices examples

Let's consider just (square) matrices with real entries. Any matrix is congruent to itself, i.e. $$A=B^TAB$$ for $B=I$. But we have also the case of orthogonal matrices $O$, where (e.g.) $I=O^TIO$, or ...
0
votes
0answers
24 views

Find $a$ inverse modulo 30, $1\le a \le 30$. For each $a$ you find, find the inverse of each $a$ that have inverse modulo 30 [duplicate]

Find $a$ inverse modulo 30, $1\le a \le 30$. For each a you find, find the inverse of each a that have inverse modulo 30 a={1,7,11,13,17,19,23,29} They got a by the fact that relative primes are ...
1
vote
2answers
48 views

Show that $4(p-5)! + 1 \equiv 0 \pmod p$

Show that $4(p-5)! + 1 \equiv 0 \pmod p$ I'm having trouble figuring out how to show this. The best I've come up with is : $$4(p-5)!\equiv (p-5)! \equiv (p-1)!\equiv -1$$ However, I'm not even sure ...
3
votes
1answer
75 views

Bijective correspondence between congruences on universal algebras

I'm reading the chapter on univesal algebras in P. A. Grillet's Abstract Algebra. In Proposition 1.9 the author states: Let $ \varphi\colon A\to B $ be a morphism of universal algebras. If $ \mathcal{...
0
votes
0answers
56 views

Kronecker-Weierstrass problem, 3x6 matrices conjugacy or congruent classes?

I'm here again with a somewhat vague and hard question our teacher asked us, we have to check and proof that for all matrices $A$ and $B$ that by applying certain simultaneous transformations, we can ...
0
votes
1answer
43 views

Do the properties of modular arithmetic apply to incongruent relations?

Can you treat incongruences as you would congruent relations? i.e. do the following theorems still apply? As an example, let's say you wanted to prove Euclid's Lemma which states: If a prime $p$ ...
0
votes
1answer
75 views

Assume that p and q are odd primes and $p \equiv q \pmod {28}$. Show that $(\frac{7}{p}) = (\frac{7}{q})$.

Assume that p and q are odd primes and $p \equiv q \pmod {28}$. Show that $(\frac{7}{p}) = (\frac{7}{q})$. Could anyone give me a hint for the solution please?
1
vote
0answers
46 views

What does it mean if algebra $A$ is free in the variety $V(A)$

I am studying chapter 14 of Burris and Sankappanavar on fully invariant congruences. In Lemma 14.7 is proved that if $\theta$ is a fully invariant congrence on $T(X)$, then for $p = q \in Id(X)$ we ...
0
votes
4answers
122 views

With the help of Chinese remainder theorem show that $ x^{144} \equiv 1 \pmod{ 323}$

With the help of Chinese remainder theorem show that $ x^{144} \equiv 1 \pmod{323}$ for all $x$ relatively prime to 323. The problem with me is that I used to use CRT when $x$ is raised to a power of ...
0
votes
1answer
96 views

How can I solve the following congruence $x^2 \equiv 9 \pmod {2^3 . 3 . 5^2}$?

How can I solve the following congruence $x^2 \equiv 9 \pmod {2^3 . 3 . 5^2}$? The problem is that I do not know the number of solutions of $x^2 \equiv 9 \pmod { 3}$, it seems like either it is zero ...

1
2 3 4 5