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
3 answers
A problem in linear congruences equation
I have solved a pair of linear congruence equations like $$x\equiv2\pmod {5}$$$$x\equiv4\pmod{7}$$
But now it is difficult for me to solve $$71x\equiv26\pmod {238}$$
Even I'm not able to think how can I start for this problem.
Please provide a hint…
Atul Mishra
- 3,136
0
votes
2 answers
How Can I Solve $2x^2+3xy+8y^2\equiv0\pmod{13}$
This problem is on Pg 135 of Adams and Goldstein's "Introduction To Number Theory". They give the answer but they don't show how to solve it. They also treat it as a Diophantine equation,so how can one get from a listing of congruence pairs i.e.,…
0
votes
1 answer
Prove that the set of integers modulo m is precisely {[0], [1],...,[m-1]}
I need to prove that each of the congruence classes listed above are different, and that any other congruence class [a](for any integer a) has to be equal to one of the congruence classes listed.
I know in order to prove the second part I must show…
Hannnnn
- 35
0
votes
1 answer
simultaneous linear congruences question
I am trying to solve a problem of the following form
Ax≡B(mod C)
A'x≡B'(mod C')
A''x≡B''(mod C'')
where A, B C are just integers. I know how to solve these problems when there is no coef on X, by changing them into linear Diophantine equations, but…
Cole
- 1
0
votes
4 answers
Find a solution or show that there is none: $x^2 \mod 7 = 3 \; (x\in \mathbb{Z})$
Find a solution or show that there is none: $x^2 \mod 7 = 3\;(x\in \mathbb{Z})$
I've tried different ways to approach this problem, such as rewriting the equation in the form $x^2 = 7k+3$, where k is an integer.
Then it becomes proving that…
Dr C
- 354
0
votes
1 answer
How do I show if a relation set R is transitive?
Consider the set $S = \{-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5\}$
And define a relation $R$ on $S$ by $(x, y) \in R$ if and only if $x +
> 2y \cong 0 (mod 3)$
Show that the relation $R$ is an equivalence relation and list the
equivalence class…
Elias
- 403
- 3
- 15
0
votes
3 answers
What does this congruent proof actually say?
I have a statement that says:
For every $n >= 2$.
If n is an odd number then $7^{n}-1$ is not divisible by 4
Prove whether the statement is true or false.
The proof:
$7\cong -1 (mod 4)$ so $7^n-1\cong (-1)^n-1\cong -1(mod 4)$ and thus 4 does…
Elias
- 403
- 3
- 15
0
votes
1 answer
Help with finding $x,y \in \mathbb{Z} $ such that work for statement with reminders
So I have an expression $18x+14y$ and I have to find such $x,y \in \mathbb{Z} $ that expression $18x+14y$ , when divided by 63, will have a reminder 5.
So I know that I have to solve this equation:
$$18x+14y\equiv 5 (mod63)$$
But I don't know how to…
MathIsTheWayOfLife
- 2,091
0
votes
3 answers
Find the residue to divide $2^{3^{2011}}$ between $17$
help with this excercises.
Find the residue to divide $2^{3^{2011}}$ between $17$
I try:
$$3^3 \equiv 10(mod\ 17)$$
$$3^{10} \equiv 8(mod\ 17)$$
$$3^{120} \equiv -1(mod\ 17)$$
$$3^{2011} \equiv 7(mod\ 17)$$
Then
$$2^{3^{2011}}=2^7*2^{17k}, k\in…
mathnw
- 89
0
votes
1 answer
solve congruence for m
I just need to know is my calculation here correct. I have
$$ 4m-2 \equiv 1,2,5,6 \pmod{10} $$
and I want to find the value of m. Is it correct if I divide
through by 2, I will have
$$ 2m-1 \equiv \dfrac{1}{2},1,\dfrac{5}{2},3 \pmod{5} $$
Then,…
shahrina ismail
- 249
0
votes
2 answers
Understanding the last step in solving a linear congruence?
So I want to solve the linear congruence $$17x \equiv 3\mod 29$$
The inverse of $17 (mod 29)$ is 12, from here on, I have no clue how to solve for $x$.
I get the results
$$12*17 \equiv 1\mod29$$
$$12*17x \equiv 36\mod29$$
But I dont understand how…
Arnold Doveman
- 1,095
0
votes
1 answer
Solving simultaneous equations with different congruences
Let a, b, c be positive integers satisfying:
$$
a \equiv 0 \;(mod\;3)\\
b \equiv 0 \;(mod\;5)\\
c \equiv 0 \;(mod\;7)\\
a+b \equiv 0 \;(mod\;67)\\
b+c \equiv 0 \;(mod\;17)\\
c+a \equiv 0 \;(mod\;73)\\
$$
This problem requires the smallest possible…
ichallas
- 55
0
votes
1 answer
proof of modular congruencies
Is it possible to show that given $a,b,d,n \in \mathbb{N}$, if $a \equiv b \pmod{m}$ and $d\mid n$, then $a \equiv b \pmod{d}$?
I'm able to see it computationally by checking numbers but can't seem to formulate a proof so I'm not sure if I'm just…
greenteam
- 333
0
votes
1 answer
Is it true that if $ -p \equiv -1 \pmod q $, then $p \equiv 1 \pmod q $?
Is it true that if $ -p \equiv -1 \pmod q $, then $p \equiv 1 \pmod q $?
p and q are prime numbers.
Topolożka
- 105
0
votes
1 answer
Solving a basic linear congruence
I have been tasked with solving a linear congruence:
$$-12x\equiv-3\pmod{26}$$
How do I do this? I've never done linear congruences with minus signs so I'm quite confused.
Usually I would find the inverse of the LHS and multiply the RHS by the…
user2850514
- 3,689