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
0
votes
0answers
49 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
32 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
44 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
36 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 ...
1
vote
0answers
41 views

Find the remainder of $5^{ 5^{1000}}$ when divided by $7$ [duplicate]

Find the remainder of $5^{ 5^{1000}} $ when divided by $7.$ And the hint given is: what is $5^{1000} \pmod 6$? But still I do not understand what to do exactly; could anyone help me in tackling this ...
1
vote
4answers
62 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
58 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 ...
0
votes
2answers
69 views

without actually finding them, determine the number of solutions of the congruence.

without actually finding then, determine the number of solutions of the congruence. $$x ^2 \equiv 3 \pmod {11^2 . 23^2}$$ My professor gave a hint of finding the order of the group of units and the ...
1
vote
5answers
102 views

How can I solve $x^2 \equiv 19 \pmod {59}$.

How can I solve $x^2 \equiv 19 \pmod {59}$? I know that we can just try squaring numbers from 1 to 58 , but this is a very slow method, is not their a quicker one?
0
votes
3answers
71 views

How can I prove that $ (3/p) = -1$ if $ p \equiv \pm 5 \pmod {12}$

I know how to prove that $ (3/p) = 1$ if $ p \equiv \pm 1 \pmod {12}$ but I need to prove that $ (3/p) = -1$ if $ p \equiv \pm 5 \pmod {12}$, which the book write it as it is without explaining why ...
0
votes
5answers
43 views

How can I solve a system of 2 congruences?

I have this system of congruences $ p \equiv 3 \pmod 4$ and $ p \equiv 2 \pmod 3$ and the solution written in the book is $ p \equiv 11 \pmod {12 }$ but I do not know how? Could anyone explain this ...
4
votes
2answers
86 views

How can I know the number of solutions of the following congruence $x ^ {10} \equiv 1 \pmod {2016}$?

How can I know the number of solutions of the following congruence $x ^ {10} \equiv 1 \pmod {2016}$? My professor quick answer was: $$\mathbb{Z_{2016}^*} \cong \mathbb{Z_{32}^*} \times \mathbb{Z_{9}...
3
votes
2answers
87 views

An elaboration of how an index formula comes from another formula.

A theorem is given below (in which the book said that it is used in justifying how the index formula in question came) : And this picture contains the index formula that the author said that it ...
1
vote
2answers
59 views

Prove that for any odd integer a, $a^{33} \equiv a \pmod {4080}$

Use Euler's theorem to prove that: For any odd integer a, $a^{33} \equiv a \pmod {4080}.$ The hint given in the book is that $4080 = 15 \times 16 \times 17$, but I do not know how to use Euler's ...
0
votes
4answers
63 views

Prove that $\mathbb{Z}/ \equiv 3$ has exactly three elements.

The Definition: Let $R$ be an equivalence relation on the set $A$. The set of all equivalence classes is denoted by $A/R$. The hint I have been given: First, verify that $[5]_3$, $[7]_3$, and $[0]_3$ ...
0
votes
0answers
36 views

An elaboration of a part in the proof of a criterion for finding Carmichael numbers.

The criteria and its proof is given below: But I do not understand why $p_{i} - 1|n-1$ implies $p_{i} | a^{n-1} - 1$ if we know that $p_{i} | a^{p_{i}-1} -1$. could anyone explain this for me please ?...
0
votes
2answers
39 views

A discrepancy in understanding the proof that any Carmichael number is square free.

The proof as given in " David M. Burton " is as follows: Suppose that $a^n \equiv a \pmod n$ for every integer a, but $k^2\mid n$ for some $k > 1.$ If we let $a = k,$ then $k^{n} \equiv k \pmod n.$...
0
votes
4answers
53 views

A discrepancy in the proof that 561 is Carmichael number.

The proof is given below: But I do not understand the statement in the line before last which says "These give rise to the single congruence $a ^{560} \equiv 1 \pmod n$ where gcd(a, 561) = 1 ", I do ...
0
votes
1answer
21 views

multiplying and dividing in congruence

$$x\equiv2\ (\text{mod }6)$$ This one has solution x=2, 8, 14, ... By multiplying 2 to both sides, $$2x\equiv4\ (\text{mod }6)$$ By dividing by $2$, $x\equiv 2\...
0
votes
0answers
48 views

Find all non-trivial congruence relations on $(\mathbb{Z},+,0,-)$.

First of all, I have already proven that for every $d\in\mathbb{N}$ the relation \begin{align*} a\sim_d b:\Leftrightarrow\exists k\in\mathbb{Z}:\,b-a=kd \end{align*} is a congruence relation on $(\...
0
votes
1answer
33 views

Show that $\equiv$ is a congruence on $M\times S$

I'm sorry if a similar question has been posted before, but I was unable to find one based on my searches. This is an extra practice problem for a number theory class. I've been trying to prove this ...
0
votes
2answers
63 views

Write a single congruence?

Write a single congruence that is equivalent to the pair of congruences: $x\equiv 1(\mod4)$ and $x\equiv 2 (\mod 3)$. I am new to Number Theory/ Modular Arithmetic. Just started reading the ...
2
votes
2answers
102 views

Number Theory: Problem with proofs

There are two propositions in the chapter of Number Theory in my book, the proofs of which I am having trouble to understand. For Proposition 3 I cannot understand the proof from "Therefore ..." in ...
0
votes
2answers
50 views

If $(\alpha,\beta)$ is the factor pair congruences of algebra $\mathbb{A},$ ia $(\forall \gamma\in ConA)\alpha\circ\gamma=\gamma\circ\beta?$

Let $\mathbb{A}$ be an algebra such that $ConA$ is the distributive lattice. If $(\alpha,\beta)$ is the factor pair congruences of algebra $\mathbb{A},$ prove that $(\forall \gamma\in ConA)\alpha\circ\...
1
vote
1answer
46 views

CEP for (distributive) lattices and groups?

An algebra $A$ has the congruence extension property (CEP) if for every $B\le A$ and $\theta\in\operatorname{Con}(B)$ there is a $\varphi\in\operatorname{Con}(A)$ such that $\theta =\varphi\cap(B\...
2
votes
0answers
77 views

Solution of the congruence $X^5 \equiv 1 \pmod {25}$ with lift

Can someone explain me the right steps for the solution of this congruence using the method of the lift? $X^5 \equiv 1 \pmod {25}$ I know that I can write this as $f(x) = X^5-1 \equiv 0 \pmod {...
0
votes
0answers
24 views

Showing $\Theta_{i}$ defined on $\prod _{i\in I}\mathcal{A}_{i}$ is a congruence relation.

I am trying to use the previously asked question to help me finish my question. But I have a simple question about their "case 1" (when $a = b$). Why is it that if $a=b$, then $f(a)=f(b)$? Is this by ...
0
votes
1answer
30 views

Solve a set of congruences

John is thinking of a number $n$. He's willing to tell us that the number is close to $10000$ and in binary system it ends on $101$. In $7$ and $11$ system it ends on digit $2$ and the last two digits ...
0
votes
2answers
60 views

How to find the inverse of a number in a congruence relation

I have an equation like this : $$39x \equiv 1 \mod 257$$ To solve this I need to find $39^{-1}$ in $\mathbb{Z_{257}}$. Or am I thinking in the wrong way? How can I find the inverse of a number in a ...
0
votes
2answers
54 views

Solve linear congruences

Solve linear congruences system $11x \equiv 10 \mod 12$ $14x \equiv 10 \mod 15$ $20x \equiv 10 \mod 21$ We need to find x that is closest to 1200. The correct solution is 1250. This is the way I ...
0
votes
1answer
17 views

Applying set operations on congruent mod relation

I've been asked a question to solve about congruent modulo. But the question is very different than another congruent modulo questions I have seen so far. It wants me to apply set operations on it. ...
0
votes
3answers
27 views

Congruations - relations

Is $3n+2 \equiv 0 \bmod 4$ same as $3n-6 \equiv 0 \bmod 4$ ? I think it's the same thing because $2$ and $-6$ have the same remainder when divided with $4$.
0
votes
1answer
29 views

Finding the number that, to a given power, is congruent to given modulo

I just started learning about congruences and I stumbled on a question that asks to solve for $x$ given: $$x^3 \equiv 20 \ (\text{mod }41)$$ I got the answer to eight by simple calculation however I ...
4
votes
2answers
39 views

Simplifying powers in a congruence

Given that $k \equiv 3 \pmod 8$, determine the least residue of $$3k^{333} + 23^{999} \pmod 8.$$ So I've done some checking and I know that $3(3^{333})\equiv$ 1(mod8). (I checked it with a power mod ...
3
votes
3answers
347 views

How is $(x+y)^p \equiv x^p + y^p$ mod $p$ for any prime number $p$?

I'm currently studying for an exam and on the practice test given to us (with solutions), there is a problem that states the following: Notice that for all $x,y \in \Bbb Z$, $(x+y)^2 = x^2 + 2xy + y^...
3
votes
1answer
69 views

Questions about the system $x+c_1\equiv y \pmod z$ and $d=y+c_2$ for integers $x$, $y$, $z$, $c_1$, $c_2$

Let $x, y, z \in \mathbb Z$ and $c_1, c_2$ be two arbitrary constants (not necessarily equal). Given that $x + c_1 \equiv y \pmod z$ and $d = y+c_2$, My queries are, Can I find a general ...
0
votes
1answer
50 views

Objects of a congruence category

A congruence category is defined as follows according to Awodey's book Category Theory: We have a congruence $\sim$ on a category $C$. Then $C^\sim$ is defined as: \begin{align*} (C^\sim)_0 &= ...
7
votes
5answers
275 views

$f(x) \equiv 1$ mod $(x-1)$ and $f(x) \equiv 0$ mod $(x-3)$ then is there any $f(x)$?

Let $S$ be the set of polynomials $f(x)$ with integer coefficients satisfying $f(x) \equiv 1$ mod $(x-1)$ $f(x) \equiv 0$ mod $(x-3)$ Which of the following statements are true? a) $S$ is empty . ...
0
votes
0answers
63 views

Chinese remainder theorem - A, B and C think of a code

A, B and C are trying to think of a code. A remembers that after dividing by 13, the residue is 8. its double increased by 1234 after dividing by 17 leaves us residue of 7. C remembers that its triple ...
0
votes
2answers
29 views

How to calculate this congruency?

Let's say I have this linear congruency: $2x + 1234 = 7 \mod 17$. Without "$+1234$" I would've used the following formulas: $x = x_0 + k(\dfrac{m}{gcd(a, m)})$, whereas $ax_0 + my_0 = b$. But I don't ...
4
votes
2answers
279 views

Congruence for real numbers

I have a stupid question. I just saw $$\sqrt{2}^{p}\equiv \pm \sqrt{2}\pmod{p}$$ for all $p>2$ prime. In a sense, this is easy to verify. E.g. for $p=3$, we have $\sqrt{2}^3=2\sqrt{2}$ on the ...
0
votes
3answers
63 views

Solving a congruence/modular equation : $(((ax) \mod M) + b) \mod M = (ax + b) \mod M$

I've been trying to prove this equation for my homework. $$(((ax) \bmod M) + b) \mod M = (ax + b) \bmod M$$ We have that $a,x,b,M > 0$, and $a ≡ b \pmod M$ Reading KhanAcademy website, I found ...
0
votes
1answer
42 views

$a^2 + b^2 \equiv 0 \pmod{p}$ and $p \nmid a, b$

Let $p$ be a prime number such that $p \not\equiv 3 \pmod{4}$. Show that there exist two integers $a$ and $b$, such that $a^2 + b^2 \equiv 0 \pmod{p}$ and $p \nmid a, b$. If $p \not\equiv 3 \pmod{4}$ ...
1
vote
0answers
32 views

Lucas Reciprocity Laws

Suppose $p$, $q$ are primes such that $p=qk+1$. If $a$ is not $0$, $1,$ or $-1$, then $a^q\equiv1\pmod p$ if and only if $a$ is a $k$-th power residue modulo $p$, so that $a^{p-1}\equiv1\pmod p$. ...
2
votes
1answer
145 views

Chinese Remainder Theorem, Miller-Rabin Primality test, and more…

Good day, I was going over the proof of the Miller-Rabin Primality Test and have a few questions regarding it. THE BOOK IS COMPLEXITY AND CRYPTOGRAPHY: AN INTRODUCTION Where $B_t = \{a\in\Bbb Z_n^...
3
votes
1answer
106 views

For what values of n is $f(x) = x^3 mod(n)$ a bijection from $X={(0,1,2,…,n-1)}$ to itself.

I was thinking about shuffling, mapping ${(1,2,...,n-1)}$ to a permutation of itself using a mapping like $x\to x^k \mod(n)$ and clearly $k=2$ cannot work since $1$ and $n-1$ have the same image for ...
0
votes
1answer
29 views

Congruence relation

I did not have any number theory course, so can someone help me solve the following congruence relation for odd prime $p$ $$(-7)^{\frac{p-1}{2}} \equiv 1 \mod{p}$$ I want to find prime $p$ such that ...
0
votes
4answers
55 views

Is there any way to prove that if $4y=4x+13k$ then $y=x+13l$?

I am doing a true/false problem, and it says if $4y=4x+13k$ then $y=x+13l$. I couldn’t find any counter example so I suppose the statement is true but could not prove the above equation equivalent to $...
1
vote
1answer
38 views

Why do these 2 congruences imply the following?

Suppose the following 2 congruences hold \begin{equation*} (x + \alpha)^n \equiv x^n + \alpha \hspace{4mm} (\text{mod} \hspace{2mm} x^r - 1, \hspace{2mm} p) \\ (x + \alpha)^p \equiv x^p + \alpha \...
3
votes
1answer
29 views

notation in congruence relation

hi there i was looking through my lecture notes and i'm struggling to understand a particular piece of notation the vertical line | and i was wondering if you could explain its meaning $$f \sim g \...