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
2
votes
1 answer
Which of these congruences are correct?
a) $1082^{551} \equiv 1(\bmod 47)$
b) $1081^{552} \equiv 1(\bmod 47)$
c) $1080^{551} \equiv -1(\bmod 47)$
d) $1079^{553} \equiv 1079(\bmod 47)$
You have to use Fermat's little theorem which states that ....
if $p$ is a prime number and $a$ is a…
Arnold Doveman
- 1,095
2
votes
3 answers
Find the solution of the congruence modulo 4199
I am really bummed out on this problem, can't find any helpful links. But the problem asks:
1.) Find the solution of the congruences modulo 4199:
$x ≡ 11 \ (mod \ 13), \ x ≡ 5 \ (mod \ 17), \ x ≡ 17 \ (mod \ 19)$
I really need a good explanations on…
KonoDDa
- 123
2
votes
2 answers
If $x^5 ≡ 2 $(mod $17$) then $x ≡ 15 $(mod $17$)
How am I suppose to reduce the $x^5$ Should I write the entire table ?
Ming Wu
- 75
2
votes
3 answers
Prove that if $p$ is an odd prime and $x$ is an integer such that $x^2\equiv 1~mod~p^k$, then $x=\pm 1~mod~p^k$
I'm trying to prove the statement given in the title. I'm quite confused. I would really appreciate if someone can verify, or suggest any changes to what I've got so far.
Assume $x^2 \equiv 1~~mod~~p^k$. Then $p^k$ must divide $x^2-1$, which is…
user306691
- 135
- 1
- 8
2
votes
2 answers
Congruence Substitutions
If I'm asked to calculate $319^{566} \pmod{23}$, and I know $319 \equiv 20 \pmod{23}$, is it mathematically correct to then calculate $20^{566}$ instead? I feel the answer is yes, but I've an exam tomorrow and would rather a concrete notion rather…
John L.
- 273
2
votes
2 answers
How to solve nested congruences?
Let's say that I'm trying to solve this equation to find the valid value(s) of x:
$(x \% 5) \% 2 = 1$
I know that when you have:
$A\%B=C$
That you can rewrite it this way:
$A \equiv C+B*N$
$\forall N \in \mathbb{Z}$
So, to solve the equation, I…
Alan Wolfe
- 1,259
2
votes
2 answers
Prove that $2^{15}-1$ is divided by $11\cdot31\cdot61$?
I have to prove that $2^{15}-1$ is divided by $11\cdot31\cdot61$.
I have proven using congruencies that $2^{15}-1$ is divided by $31$. However we have
$$2^5\equiv 10 \mod{11}$$
$$2^{15}\equiv 10^3=1000\equiv 10 \pmod…
parkhyeyoo
- 177
2
votes
2 answers
Find the remainder when $3^{89}7^{86}$ is divided by $17$
Find the remainder when $3^{89}7^{86}$ is divided by $17$.
I guess the problem is to be solved by congruencies. But unfortunately, I have no clear conception about it.
Can someone please explain it.
Thank you.
Number
- 61
2
votes
1 answer
Find all solutions to $x^{10} = 1 \pmod {377}$
Find all solutions to $x^{10} \equiv 1 \pmod {377}$
I noticed that $x^{10} \equiv 1 \pmod {377}$ can be written as:
$(x^5+1)(x^5-1)\equiv 0 \pmod {377}$
also $377 = 13 \times 29$
Any help would be greatly appreciated
mike russel
- 311
2
votes
2 answers
Proof with congruence and primes
So here it goes.
For any integer $p > 1$, if $(p - 1)!$ is congruent to $-1 \pmod p$ then $p$ is prime.
Any help would be appreciated!
andrew749
- 215
2
votes
3 answers
Proving $n^{17} \equiv n \;(\text{mod}\; 510)$
As the title says, prove that $n^{17} \equiv n \;(\text{mod}\; 510)$. I know that you need to use the fact that $510 = 2\cdot 3\cdot 5\cdot 17$, but I can't figure out how. I've found a similar question on this forum, but can't make any sense out of…
wlyles
- 239
2
votes
1 answer
Two congruence. Are they true?
Let $p$ be prime, $n \in \mathbb{N}$, $l \in \mathbb{N}$
The first one:
$$ n \neq pl \implies \forall k\in \mathbb{N} \ \ n^{\phi (p^k)} \equiv 1 \pmod p. \\
$$
And the second one:
$$ (1+n)^p = 1+ n \mod p. $$
Are they true?
user180834
- 1,453
1
vote
3 answers
How the find the smallest positive solution of $353x\equiv 254\mod 400$?
The method that I'm trying to follow is that x = 254 x 353$^{\phi(400)-1}$ where $\phi$ is the Euler's totient function. But how do we find the lowest possible solution?
Ankit
- 13
1
vote
1 answer
About a new type of congruence system.
If $A\equiv B\pmod m$ then m|(A-B). What if you used a 2 coordinate congruence where $C\equiv D\pmod {m,n}$ then there exists R,S such that (C-D) = m R+n S, where R and S are coprime and |mR+nS| > gcd(m,n). So if $A\equiv B\pmod {m,n}$ then…
user128932
- 543