For questions about congruences in modular arithmetic, concerning for example the chinese remainder theorem, Fermat's little theorem or Euler's totient theorem.
Questions tagged [congruences]
1724 questions
0
votes
2 answers
Method to Solve Linear Congruences
Can someone walk through how to solve $17x \equiv 7 \pmod{35}$? I'm having a lot of trouble with this and finding multiplicative inverses.
I tried $\mathbf35 = 5(7) + 0$, but I'm not sure what to do since the remainder is 0
John
- 217
0
votes
2 answers
Find all solutions of the equation $x^2+x=0$ in $\mathbb Z_6$
As in the title, I'm trying to find all the possible solutions to the equation: $x^2+x=0$ in $\mathbb Z_6$.
I know that the solution for the congruence equation is valid only if $m |(b-a)$. I assume that the equation is already in that form, so the…
user306691
- 135
- 1
- 8
0
votes
1 answer
If $y\equiv 1 mod 4$ then $y^2 \equiv 1 mod 8$
Given $$
y\equiv 1\ mod \ 4
$$
How can i proove that
$$
y^2\equiv1\ mod\ 8
$$
greedsin
- 571
0
votes
2 answers
Prove that $5a^2 \equiv k \bmod 12$ where $k \in \{0,5,8,9\}$.
Prove that $5a^2 \equiv k \bmod {12}$ where $k \in \{0,5,8,9\}$.
Hence show that the equation $24x^7 + 5y^2 = 15$ has no integer solutions.
I think I need to evaluate each case with the $k$ values first but not sure how...
0
votes
2 answers
Understanding issue on demonstrating the congruences theorem
I've been working on congruences these days and figured out the core concept behind this notion. However I fail to understand a part of the demonstration:
Part 1 was about proving that if $a\equiv b\pmod n$ then $n$ divides $a-b$. I got it, it was…
Erulk
- 15
0
votes
2 answers
Is this correct? Is there a faster way to demonstrate it?
here are the instructions:
1) Prove that if $n$ is an even natural integer, then $n^2\equiv 0\pmod4$
2) Prove that if $n$ is an odd natural integer, then $n^2\equiv 1\pmod4$
1) If $n$ is even then it equals to $2k$ where $k \in…
Erulk
- 15
0
votes
2 answers
What is $2^7 + 3^8 \bmod 11$?
What is $2^7 + 3^8 \bmod 11$?
What is the most important thing that i should think of first when am faced with such kind of a problem. My tutor was like $2^7 = (2^5)(2^2)$. But why not raise it to different powers like 4 and 3 instead?
Hakim Marley
- 221
0
votes
1 answer
Solve the system of congruences help?
I am really struggling with how to solve systems of congruences and I have a problem I need to solve as well as some attempt to solve it so any additional help would be so greatly appreciated!
Equations:
x = 3 mod 4
x = 4 mod 5
x = 6 mod 7
I…
CKCMathCS613
- 23
0
votes
2 answers
Equivalence of congruences - why are these congruences equivalent?
I'm reading a solution of the following congruence: $x^{59} \equiv 604 \mod 2013$. It says that it is equivalent to the following system of congruences:
$$\begin{cases} x^{59} \equiv 604 \mod 3 \\ x^{59} \equiv 604 \mod 11\\ x^{59} \equiv 604 \mod…
qiubit
- 2,313
0
votes
1 answer
Solve linear congruence: $ax + b = y \; (mod \; m)$
I am trying to solve $ax + b = y \; (mod \; m)$ for x, where $a,b,y,m$ are known values. This corresponds to running a linear congruential generator in reverse for one iteration.
I am happy to assume that $gcd(a,m) = 1$, which according to this…
user154230
0
votes
2 answers
Consider the system of Congruences $x \equiv a \pmod{m}$ and $x \equiv b \pmod{n}$
I want to prove that this system has a unique solution $\pmod{\frac{mn}{g}}$, where $g= \gcd(m,n)$ provided that $g \mid b-a$
Here is my attempt.
From $x \equiv a \pmod{m}$ we know that $m \mid x-a$ and so there must exists an integer $k$ such that…
alkabary
- 6,214
0
votes
1 answer
Modulus equation
I never seem to be able to understand this subject.
"Give an expression for x when x(mod n) = x(mod m), while n and m are positive integers and n < m."
My attempt:
x(mod n) => x = an + c => c = x - an
x(mod m) => x = bm + y => y = x - bm
x(mod n)…
Arcthor
- 91
0
votes
0 answers
Is it possible to get nontrivial $n$ such that we can find BOTH $n \pmod p$ and $\log{(n)} \pmod p$?
If we are looking for a value $n \equiv v \pmod p$ or $n \equiv v_r + v_i i \pmod p$, where $v_r+v_i\cdot i$ is a complex number modulo $p$, is it ever possible to have a situation where we can find both $n$ and $\log{(n)}$ modulo $p$? I know that,…
Matt Groff
- 6,117
0
votes
2 answers
Getting the General Solution of Linear Congruence
$4x \equiv 12 \pmod {26}$
I have this equation and I understand that it has two solution via $\text{gcd}(26, 4)$.
One of the answers is $x\equiv3$, which I can get by multiplying both sides by inverse of $4$. But the other answer which is…
raz789
- 49
-1
votes
1 answer
Prove that for each odd $m> 2$, is true that $\displaystyle \sum_{k=1}^{m-1} k \equiv 0 \pmod m$
please, know somebody solution for this argument?
Prove, that for each odd $m > 2$, it is true that $$\sum_{k=1}^{m-1} k \equiv 0 \pmod m$$
Thanks for yours answers!
Dr. Zoidberg
- 31