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
1 answer
Discrete maths congruences question
"By the definitions of modm and of congruence modulo m, we know that a ≡
(a mod m) (mod m) and b ≡ (b mod m) (mod m)."
why is a ≡ (a mod m) (mod m), is there a proof for this?
0
votes
2 answers
Two congruence both be satisfied
Can "a is congruent to c(mod b)" and "a is congruent to -c(mod b)" both be true at the same time? I think they cannot both be true, but I am wondering the reason why they cannot.
Slavica
- 99
0
votes
2 answers
Modular congruence rules
May take exponent of both sides of a modular congruence?
For instance, may I write
$$n^2\equiv-1\mod p \quad \rm as \quad(n^2)^{2k+1}\equiv (-1)^{2k+1}\mod p ?$$
Slavica
- 99
0
votes
1 answer
What is the order of operations for testing congruency mod(x)
I'm reading the Wiki page on congruence relation and am trying to figure out
"Do I take the mod(x) before or after the addition or multiplication operation"
BTW - When I tried to figure this out on my own, I realized that n in mod n would be…
makerofthings7
- 567
0
votes
2 answers
Why is $5t +1\equiv 2 \pmod 6$ equivalent to $t \equiv 5 \pmod 6$?
I feel like I am missing something really obvious here but I can't explain why these two are equivalent. I understand that $5t \equiv 1 \pmod 6$ but I can't make the next step.
Kom
- 303
0
votes
2 answers
Suppose that $a$ is co-prime to $n$. Prove that there exists $z ∈ Z$ such that $az \equiv 1 \pmod n$
So here's the question:
Suppose that $a$ is co-prime to $n$. Prove that there exists $z ∈ Z$ such that $az \equiv 1 \pmod n$
So, what I was thinking was that by Bezout's Lemma, we have hcf$(a,n)=1$ and so $az=n-1$ but the I can't turn that to a plus…
Dan D'silva
- 169
0
votes
1 answer
multiply solution of linear congruence equation
let us consider the following theorem
i am surprised about this theorem because if we take for instance following equation
and if we divide both side by 2, we will get
one solution is 3 and another solution is 7, but there another solution …
dato datuashvili
- 9,194
0
votes
0 answers
Exponential congruence for a public key
I have this formula as a public key for "T" = 19:
$c \equiv 19^{13}(mod 697)$
But I do not know how to solve it. I tried the exponential property:
$716\equiv 19(mod 697) \Rightarrow 716^{13}\equiv 19^{13}(mod 697)$
But as it turns out, c = 15.
So,…
0
votes
3 answers
Formula for the modular inverse
We all know the formula for the modular inverse: $a\bar{a} \equiv 1$ (mod m), but sometimes you see the formula $\bar{a}\equiv a^{\phi(m)-1}$ (mod m).
How do you become $\bar{a}\equiv a^{\phi(m)-1}$ (mod m) from $a\bar{a} \equiv 1$ (mod m)?
WinstonCherf
- 1,022
0
votes
1 answer
Grouping in blocks by exponential Ciphers
Public key: $(e,n) = (17, 1 066 601)$
Private key: $d = 939 293$
Message: 452423293428
Table:
Digital signature:
I want to decrypt and encrypt the message by:
$P = C^d (mod 1 066 601)$
$C = P^e (mod 1 066 601)$
My book says, I have to group the…
WinstonCherf
- 1,022
0
votes
2 answers
Congruence modulo 37 using Euler's theorem (maybe).
How would one show (preferably using congruences) that $$37\not\mid n^{9^9}+4 $$ for any $n \in \mathbb Z$?
user492757
0
votes
1 answer
If possible, find the solution to the two congruences:
(a) $10X + 12Y − 8Z ≡ 14 \pmod 8$
(b) $3X − 15Y + 24Z ≡ 13 \pmod {81}$
So I see this is a system of equations and I take the equations and did:
$(b)-3(a)$ which yields:
$33X +21Y ≡ -29 \pmod {81-8}$ ?
I'm unsure of if I can directly compute…
Bugcatcher123
- 111
0
votes
2 answers
Find all solutions (if there are any) to the following congruences
Find all solutions (if there are any):
$x^2 \equiv -1 \pmod{7}$
I found $x$ $\equiv$ $\sqrt6 \pmod{7}$
Is this the answer?
Can I use the same procedure for $x^2 \equiv -1 \pmod{13}$
jiqiudabao
- 361
0
votes
0 answers
solve congruence equation with 4 parameters
have the following equation: $(7i_2+13j_2+15)+(i_1+j_1+2)$ must be divisible by 18. The variables $ i_1, i_2$ and $j_1, j_2$ can take values 0,1,2,3,... if we pair the variables $(i_1,j_1)$ and $(i_2,j_2)$ then in a given interval, say 0-1000 (i.e.…
bijan karimi
- 29
0
votes
3 answers
How do I solve a congruence system that doesn't satisfies the Chinese Remainder Theorem?
I have the following system
$ x \equiv 2 (mod 4)$
$ x \equiv 2 (mod 6) $
$ x \equiv 2 (mod 7) $
And I can't apply the Chinese remainder Theorem.
I tried applying the Chinese remainder Theorem to the last 2 congruences, which gave me that the set of…
