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
1
vote
1 answer
Sum of fifth powers using congruences
How would one find n via congruences (i.e, not by calculating)? $$133^5+110^5+84^5+27^5=n^5$$
I know it's 144, but how do you find it?
user492757
1
vote
1 answer
What is the general method for solving congruences of the form $x^2\equiv a \bmod p$, where p is prime?
For example $x^2 \equiv 13 \bmod 29$. The only solution that comes to mind is to just calculate the squares of all of the numbers from 0 to 28, but that's tedious. Is there a better method?
EDIT: the question that this is marked as a duplicate to…
Joald
- 625
1
vote
1 answer
Congruence equation with rational expression
How can I solve for F in the following situation?
$$ F \equiv \frac{n}{d} \pmod{m} \tag 1$$
Denominator d always divides n, but I cannot reduce the fraction directly because n is always huge, and I would need to do modular operations on it first.…
BoLe
- 369
1
vote
1 answer
Triangles within a Parallelogram
ABCD is a parallelogram.
E is the point where the diagonals AC and BD meet.
Prove that triangle ABE is congruent to triangle CDE.
Charlie
- 303
1
vote
1 answer
Wilson's Theorem Problem
How can we proof that if $p$ is prime and $k$ is integer number that $1
user426865
- 15
1
vote
4 answers
Solve a congruence $1978^{20}\equiv x\pmod{125}$
I have checked the solution ($x=26$).
Solving modulo $5$ gives
$$1978^{20}\equiv 1978^{2\cdot 10}\equiv 1\pmod{5}$$
Solving modulo $25$ also gives
$$1978^{20}\equiv 1\pmod{5}$$
How to evaluate the remainder $x$?
user300045
- 3,449
1
vote
2 answers
Find all solutions $ x $in $Z$ to the simultaneous congruences for $x=1 (mod 2)$ and $x=2 (mod 3)$
In the first part of the question, it asks for 1 solution, so I just made $2k+1=3l+2 $ and found that $k$ is $2$ and $l$ is $1$, so $x=5$.
But what does that mean to find "all" solutions for this?
George S
- 359
1
vote
3 answers
Necessity of the condition $\gcd(a,n)$ divides $b$ for solving $ax\equiv b\pmod{n}$?
I was wondering if someone could give me some more intuition on why we need that $\gcd(a,n)$ divides $b$ when we want to solve $ax\equiv b\pmod{n}$?
user357325
- 13
1
vote
1 answer
Solving higher congruence
How do you go about solving $x^{11} \equiv 5 \pmod{41}$.
I'm very new to this topic and have watched numerous YouTube tutorials with not much luck so far.
Thanks in advance.
patrickdahal
- 11
1
vote
1 answer
Solve $3y + 2 \equiv 3\ (5)$ in math exercise
I'm stuck at the ending part of a math exercise on congruences.
I must solve the following system of congruences $S$:
$x \equiv 2\ (3)$
$x \equiv 3\ (5)$
I was first asked to give the remainders of the division of $3y +2$ by 5, with knowing the…
Dhazard
- 123
- 2
- 11
1
vote
1 answer
System of linear and quadratic congruences
Solve the system:
$x^2+x+1\equiv 0\pmod {7}$
$2x-4\equiv 0\pmod {6}$
Completing the square for first equation gives:
$$(2x+1)^2\equiv 4\pmod {7}$$
$$y^2\equiv 4\pmod{7}\Rightarrow y_1=2,y_2=5$$
$$2x+1\equiv 2\pmod{7}\Rightarrow (2,7)=1|7\Rightarrow…
user300045
- 3,449
1
vote
2 answers
Do 18*37^211 and 17+12^99 have the same remainder when divided by 24?
How do you solve this using properties of congruence?
user287942
1
vote
1 answer
Using Fermat's little theorem to find $9^{45} \mod 23$
I used Fermat's Little Theorem to find:
$$9^{45} \mod 23$$
What I have done so far:
$$9^{45} = (9^2)^{22}9$$
$$9^{22} \equiv 1 \pmod{23}$$ According to Fermat's Little Theorem.
So, now I have:
$$9^{45} \equiv (9^2)^{22}9 \equiv 1^2 9…
Julia
- 496
1
vote
2 answers
Is this a correct solution to the linear congruence?
I want to solve this linear congruence:
$$2x \equiv 5 \pmod{9}$$
Backward substitution:
$$9 = 4 \cdot 2 + 1$$
$$4(-2) + 9 = 1$$
Therefore, the inverse is: $-2$
Now multiply the linear congruence with $-2$
$$(2)(-2)x \equiv (-2)5 \pmod{9}$$
$$x…
Julia
- 496
1
vote
3 answers
How to determine congruence manually
How is it possible to determine if the the following congruence is true manually?
$$
2015^{53} \equiv 8 \pmod{11}
$$
bockzior
- 135