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
2 answers
Solve equation of second degree - congruence
I have following equation:
$$n^2 - n + 2\equiv 0\pmod{49}$$
So I get:
$$n^2 - n + 2\equiv 0\pmod{7}$$
The only number is:
$$n\equiv 4 \pmod7$$
Thus, I used Hensel's Lemma. And according to (3) point…
xawey
- 381
1
vote
4 answers
Modular Arithmatic - Solving congruences
I'm sure this is pretty basic but I'm struggling to understand how to go about solving this problem for my homework. The question states "Solve the following congruences for x". The first problem is $2x+1\equiv 4\pmod 5$.
aneorddot
- 97
1
vote
0 answers
prove this Congruent equation
The question is:
if p is prime and odd number, prove that:
$1^{p-1} + 2^{p-1} +\ ... \ + (p-1)^{p-1} \equiv p + (p-1)! \ (mod\ p^2)$
I have no idea about this.
I was trying to use Wilson but no success...
ReZa
- 189
1
vote
1 answer
Congruent Equation Prove
I was trying to prove this equation
I did these but I don't know what to do next?!
$2^a-1\equiv 2^{a\ \bmod\ b}-1 \ \bmod\ (2^b -1)$
My solution:
$$ a = cb+r$$
$$ 2^{cb+r} \equiv 2^r (\bmod \ 2^b -1) $$
$$ 2^{cb} \equiv 1 (\bmod \ 2^b -1) $$ (in…
ReZa
- 189
1
vote
2 answers
How to solve this quadratic congruence equation?
Well, we have :
$$n^2+n+2+5^{4n+1}\equiv0\pmod{13}$$
i'm little bit confused, I think i can solve this using the reminders of $n^2$, $n$ and $5^{4n+1}$ over $13$, by the way I have no idea about the Chinese Reminder Theorem no need to use it. and…
Hedwig
- 153
1
vote
2 answers
Find all the integers that satisfy a system of congruences?
I have a doubt about systems of linear congruences: if I have solved the congruences and I have found as answers (for example) $x \cong8 \ (mod \ 12) $ and $x \cong 6 \ (mod \ 14)$, how can I find ALL the $x \in \Bbb Z$ that satisfy both equations?…
user149448
- 25
1
vote
2 answers
Composite Integers modulo zero
Let $m \ge 2$ be a composite integer. Prove that there are elements $[x]_m$ and $[y]_m$ of $\mathbb Z$/m $\mathbb Z$ with $[x]_m,[y]_m$ $\neq$ $[0]_m$, such that $[x]_m\cdot[y]_m=[0]_m$
So, I understand the question but I am unsure of the approach…
Benji_Bombadill
- 341
1
vote
5 answers
A way of finding $x \in \mathbb{Z}$, congruency
I'm trying to find all $x \in \mathbb{Z}$ that satisfies this equation
$$3x \equiv 1 \pmod 6$$
I tried using trial and error, but couldn't find a suitable number for x.
I know that the $\mbox{gcd}$ is $3$.
How would I approach this?
iaio942
- 13
1
vote
5 answers
Find $r\in\Bbb Z$ for $4^{451}\equiv r\mod 7$
I guess I should start by saying that $4\equiv 11\mod 7$, but I don't know how to proceed from here.
Is it possible to do without using Fermat's theorem?
Thank you.
user126638
- 79
1
vote
4 answers
$18 x \equiv 43 \pmod {23 }$.
Slightly similar to a question I submitted a few minutes ago, however this time my value for $x$ is $-602$, and I'm not sure how to write the general solution for $x$ .. help please?
Help
user122661
- 983
1
vote
1 answer
Let $n \geqslant 3$. Show that the equation $x^2 \equiv 1 \pmod{2^n}$ has exactly $4$ solutions modulo $2^n$
Okay, so I've been trying for hours to try prove this
Let $n \geqslant 3$. Show that the equation $x^2 \equiv 1 \pmod{2^n}$ has exactly $4$ solutions modulo $2^n$.
I tried using induction but I just can't work it out, I think I'm just missing…
Madmarkshero
- 47
1
vote
1 answer
How to solve $9^{89}\equiv x\mod{1000}$ for $0\leq x\leq 999$ without calculating $9^{89}$
Is there a method I can use to get an answer without having to resort to using Wolfram Alpha to calculate $9^{89}$ and taking the last three digits?
Mirrana
- 9,009
1
vote
1 answer
Congruence equation of the form $ax^2 \equiv 1 \pmod{p}$
I'm trying to solve $13j^2 \equiv 1 \pmod{264}$.
Now I've seen the form $x^2 \equiv n \pmod{m}$ but the form $ax^2 \equiv n \pmod{m}$ although it looks like a quadratic congruent equation, I don't seem to be able to follow exactly the same steps as…
Yoni
- 29
1
vote
1 answer
Given odd positive integer, $n=2m-1$, $n \equiv 1 \pmod 4 \implies m \equiv 1 \pmod 2$
$n=2m-1\implies n+1=2m$. So, $n\equiv 1\pmod 4, 2m=n+1\equiv 2\pmod 4\implies 2m=n+1\equiv 0\pmod 2$ $\implies n\equiv -1\pmod 2\implies n\equiv 1\pmod 2$. But, how to find $m$ from this last line of equivalence relations is not clear.
jitender
- 707
1
vote
2 answers
What is a congruence equation for this problem
Problem:
A factory uses 10 types of a box to package its product. They are numbered from 1 to 10. In box 10, 6 boxes of type 9 can be placed. In box 9, 6 boxes of type 8 can be placed, ... in box 2, 6 boxes of type 1 can be placed and finally in…
Ahmad
- 383