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
Solving a second degree congruence relation
Suppose $n = pq$ where $p$ and $q$ are distinct odd primes. Let $r$ be an integer such
that $r \equiv p^{-1} \pmod q$, and put $s = 1 − 2rp$. Let a be an integer such that $(a, n) = 1$.Show that the solutions modulo n to the congruence
$$x^2 ≡ a^2…
mike russel
- 311
1
vote
1 answer
Some congruences and conclusion.
Let consider this situation:
$$ \gcd (b, m) = 1 \tag{$*$} \\
b^a \equiv 1 \\
b^c \equiv 1 $$
Assume that $ a \le c $
Whether it is reasonable to draw a conclusion that is $c = ak$ for some $k$? Why? Is the $(*)$ condition is necessary? Why?
user180834
- 1,453
1
vote
2 answers
Basic congruence help
If I have that $a \equiv b$ mod $m$, then how do I show that $4a \equiv 4b$ mod $m$?
I understand for $4a \equiv 4b$ mod $m$ that must mean $m|(4a-4b)$, but I don't unsterstand how I would prove it.
Any help would be fantastic.
Bipod
- 21
0
votes
1 answer
Finding all solutions to congruence equation
my math professor gave us the following question on a past quiz and I didn't get it right and now I want to know how to do it:
Find all the solutions to the congruence x^2 is equivalent to 1 mod 437 where
mod 437=19*23.
I know I have to use the…
user167333
0
votes
1 answer
Can't Solve this Indices Question
I been surfing all related stuff concerning solving indices but all I got are congruence solved using indices and I don't even know if that's the one i'm looking for. I'm trying to solve this question:
Can anyone point me out to the right direction…
rockStar
- 103
0
votes
2 answers
how to solve to congruence $x^{98}\equiv99\pmod{125}
I show you my attempt:
$$(125, 98) = 1 \Rightarrow(x^{98} , 125) = 1 \Rightarrow (x, 125) = 1$$
(Euclidian Algorithm)
$$x^{\phi(125)} = x^{100} \equiv1\pmod{125} \wedge x^{98} \equiv99(\mod 125) \Rightarrow x^2\equiv99 \pmod{125} \Rightarrow x^2…
xawey
- 381
0
votes
1 answer
How to solve system of congruence?
I think about solution to this system of congruence.
Could you give me a clue ?
taxer
- 11
0
votes
4 answers
Finding the smallest $x$ given a set of congruence conditions.
Find the smallest integer $x$ such that
$$x \mod 5 = 3\\ x \mod 7 = 4\\ x \mod 9 = 6$$
Can you tell me how to solve this type of question? I don't need a solution.
Clearly the smallest $x$ for the first one is $8$. The smallest $x$ for the…
Saturn
- 7,191
0
votes
3 answers
How many solution this equation has?
I'm trying to solve the following equation in $\mathbb{Z^2}$ as i asked to do :
$$(x+1)^2=9+5y$$
but actually this equation has more than two solutions ... what does $\mathbb{Z^2}$ stands for ?
Hedwig
- 153
0
votes
3 answers
System of congruences?
Find all the integers $x\in \mathbb{Z}$ that satisfy the following system of equations (that is, the solution has to satisfy both equations simultaneously):
$2x\equiv 1 (mod7)$
$x^{2}\equiv 1 (mod 5)$
Any help is appreciated
user132226
- 161
0
votes
4 answers
Solve $33x≡9$ (mod 29)
I'm having trouble solving congruences. I can't seem to find a method (a series of steps) to follow in order to find the solutions of a linear congruence. In particular, I have $33x≡9$ (mod 29). My thoughts: gcd (33,29) $=1$, so there is one…
flt0102
- 1
0
votes
1 answer
Doubt concerning Fermat's little theorem with a nonprime number
I'm trying to find the residue of $\frac{64^{82}}{12}$. This means that I need to find $m$ such that $64^{82} ≡_{12} m$. Using Fermat's little theorem, I have $6^11 ≡_{12} 1$. However, 12 is a nonprime number, so my question is: how can I find…
flt0102
- 1
0
votes
2 answers
Simple Congruence Question Using Fermat's Little Theorem
Find the units digit of $3^{100}$ by use of Fermat's theorem. Would it suffice to show that because 2,5 are both prime, we can use Fermat's little theorem to show that $3^{100}\cong1(\mod{2})$ and $3^{100}\cong1(\mod{5})$, then…
H5159
- 969
0
votes
1 answer
Coprimes and Congruence
I need help getting a proof, I don't want solution to the problem just help guiding me to complete the proof.
Suppose $m,n$ are coprime, Prove that $a \equiv b \mod{mn}$ if and only if:
$a \equiv b \mod{m}$, and
$a \equiv b \mod{n}$.
0
votes
1 answer
Are the following congruences true?
For $a,b,c,d,m \in\Bbb Z$
If $a\equiv b\mod m$ and $c\equiv d\mod m$
Are the following two statements true?
$a +c \equiv b+d\mod m$
$a*c\equiv b*d\mod m$
The books I come across only list the above for $c=d$, so I wanted to know if these were true…
