For questions about congruences in modular arithmetic, concerning for example the chinese remainder theorem, Fermat's little theorem or Euler's totient theorem.

learn more… | top users | synonyms

0
votes
0answers
10 views

Proofs of congruence relations

Exercise 2.3 from "Introduction to Mathematical Cryptography" Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$ of order $r$. (a) Suppose that $x = a$ and $x = b$ are both integer ...
0
votes
3answers
19 views

What to do if the modulus is not coprime in the Chinese remainder theorem?

Chinese remainder theorem dictates that there is a unique solution if the congruence have coprime modulus. However, what if they are not coprime, and you can't simplify further? E.g. If I have to ...
3
votes
4answers
64 views

Remainder when ${45^{17}}^{17}$ is divided by 204

Find the remainder when ${45^{17^{17}}}$ is divided by 204 I tried using congruence modulo. But I am not able to express it in the form of $a\equiv b\pmod{204}$. $204=2^2\cdot 3\cdot 17$
0
votes
2answers
37 views

Solve the following congruence: $x(x+1)(x+2) \equiv 0 \pmod{221}$

Find the first five solutions for, $$x(x+1)(x+2) \equiv 0 \pmod{221}$$ I am very confused. By CRT, $x(x+1)(x+2) \equiv 0 \pmod{13}$ and $x(x+1)(x+2) \equiv 0 \pmod{17}$ But these two ...
2
votes
1answer
66 views

Solving $x^2 \equiv -x\pmod{2015}$

Problem: Find all integer solutions of $x^2 \equiv -x \pmod{2015}$. I proceeded this way: first, I realized that $2015 = 5 \times 13 \times 31$. I rewrote $x^2 \equiv -x$ as $x^2 + x \equiv 0$. ...
0
votes
2answers
34 views

$17x+11y \equiv 7 \pmod {29}$ and $13x+10y \equiv 8 \pmod {29}$. What are x and y?

Congruency question: if $17x+11y \equiv 7 \pmod {29}$ and $13x+10y \equiv 8 \pmod {29}$, we need to find $x$ and $y$. There may be more than one answer. Not sure how to go about this; any help ...
1
vote
2answers
46 views

Why is $x^2 \equiv 1 \pmod{x+1}$ for $x > 0$?

One day my mind wandered off and came upon the following. $x^2 \equiv 1 \pmod{x+1}~\forall x>0, x \in \mathbb{Z}$. My markdown might be a little bit broken :) I tested this out in Python for the ...
0
votes
1answer
25 views

Prove that the Gaussian integer $a$ is a prime element if $N(a)=p$ or $p^2$ where $p$ is congruent t0 3 mod 4

Let $a \in \mathbb{Z}[i]$ such that $N(a)$ is a prime or the square of a prime congruent to 3 modulo 4 in $\mathbb{Z}$. That is, $N(a)=p$ or $p^2$ where $p \equiv 3 \bmod 4$. Prove that $a$ is a ...
1
vote
2answers
26 views

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$. I am able to work out the solution using Euclidean algorithm techniques, but the signs on the expression do not match up with the initial ...
1
vote
1answer
35 views

Last 3 digits of Marsenne numbers

Marsenne numbers are of the form $2^{p} - 1$, $p$ is a prime. Last $3$ digits can be obtained from $2^{p} - 1 \equiv x \pmod {1000}$. This is equivalent to $$2^{p} - 1 \equiv x_1 \pmod 8\tag1$$ and ...
0
votes
1answer
22 views

Modulus Notation Division

I have a couple of silly questions (it will definitely demonstrate my lack of ability in mathematics :P) Is there a type of reduction or absorption of modulus in congruence equations? Here's an ...
7
votes
4answers
132 views

Find the remainder when ${{5^5}^5}^5$ is divided by $24$

Find the remainder when ${{5^5}^5}^5$ is divided by $24$ I tried using congruence modulo. $$5^2\equiv1\mod{24}$$ $$5^5=125\mod{24}$$ But this does not give the correct answer.
3
votes
2answers
30 views

If $p\equiv3 \pmod4 $, then there does not exist any integer $x$ with $x^2 ≡ −1 \pmod p$.

Suppose that $p$ is a prime number that that $p\equiv3 \pmod4 $. Prove that there does not exist any integer $x$ with $x^2 ≡ −1 \pmod p$. I am looking to use Fermat's Little Theorem but not able ...
0
votes
1answer
19 views

Quadratic residues and euler equation

Let $p$ be an odd prime and let $(a,p)=1$. There is no guaranteed that there is a solution to $$x^2\equiv a \pmod p$$ What is wrong here: $$a^{(p-1)/2}≡(x^2)^{(p-1)/2}\equiv x^{p-1} \pmod p$$ It is ...
1
vote
2answers
45 views

Path needed for solving these linear equations in Zn (my example Z105)

So these are two equations : $$49x \equiv 21 \pmod {105}$$ $$64x \equiv 21 \pmod {105}$$ I should find the multiplicative inverse of $64$ and then $49$ that gets the result of $1$ so.... In the ...
8
votes
3answers
254 views

Finding the solution of a congruence.

Solve the congruence $$4x\equiv16\mod{26}.$$ How do I find the solution to this? I have tried by the euclidean algorithm but the gcd is not $1$ so it doesn't work. $$\begin{align} ...
0
votes
2answers
15 views

Mensuration and similarity

Cone P has a volume of 108cm^3 Calculate the volume of 2nd come , Q , whose radius is double that of cone P and its height is one-third that of cone p Here's my working .... $$V_Q=\frac13 \pi (2r)^2 ...
-2
votes
1answer
20 views

Show that if [b] and [c] are both multiplicative inverses of [a] in Z_n then b = c(mod n).

I am having some trouble getting started with this problem. I know that I am going to need the following proposition in the proof: Let n > 0 be an integer. Then the following conditions hold for all ...
0
votes
1answer
16 views

Finding other solutions to diophantine equations

I understand how to find the first solution to these equations but can't grasp how the other solutions are found. E.g. $102x\equiv 12 \pmod{174}$ So I can find the $gcd(174,102)=6$ (showing that ...
0
votes
1answer
31 views

How to find $n$ if $a^n \equiv r \pmod m$

In particular I'm looking at the problem: \begin{align*} 3^{n_1} &\equiv 1 \pmod 4 \\ 5^{n_2} &\equiv 1 \pmod 4 \\ 7^{n_3} &\equiv 1 \pmod 4 \\ \end{align*} And I want to find $n_1, ...
1
vote
1answer
25 views

Prove that $\sigma^*$ is the least group congruence on $S$

Let $S$ be an inverse semigroup and consider the relation $\sigma$ on $S$ given by $$a \sigma b \iff ab^{-1} \in E(S)$$ Consider the congruence generated by $\sigma$, say $\sigma^*$. Prove that ...
0
votes
2answers
49 views

Congruence for large modulus

The idea it to find remainder $35^{32} + 51^{24} \bmod 1785$. 1785 is a composite number equal to 3 x 5 x 7 x 17. 35 is 0 mod 5 and mod 7. 51 is 0 mod 3 and mod 17. Any help regarding steps from ...
2
votes
0answers
29 views

Fermat's little theorem and Euler's criterion

Is it possible to find the solution of this congruence by Fermat's little theorem and how ? $$15125^{2401}\pmod {72}$$ Can somebody tell me how to do it by Euler's criterion?
0
votes
2answers
42 views

Find $x \in{Z_{250}}$ so that $ x\equiv{248^{156,454,638}} \pmod{250}$?

I am looking for a easy way to solve it, without use the computer. I did that but with the computer. $GCD(250,248) \ne 1$ So I did: $250 = 125*2$ $248^{156454638}$ (mod 250) = $248^{156454638}$ ...
0
votes
2answers
36 views

Quadratic Reciprocity and Congruences

I have to find the result of congruences : $$(a)\left(\frac{34}{73}\right)$$ $$(b)\left(\frac{36}{73}\right)$$ $$(c)\left(\frac{1356}{2467}\right)$$ By the way,I found that Theorem of Quadratic ...
0
votes
2answers
24 views

How do i show this :for every prime $p> 3$ and every integer $k\geq1$ ,${p}^{4k}=1\mod3$?

There are many formula which are a multiple of $3$ for example $n^3+2n$ ,I accross this formula " ${p}^{4k}=1\mod3$" after some computations in WA then My question here is: How do i show this if it ...
1
vote
0answers
26 views

When is the sum of three reduced rationals equal to an integer

When is the sum of three reduced rationals equal to an integer? This may be a duplicate of Question 1550437 but even if it is, there is no answer associated with this other question. Given three ...
2
votes
1answer
20 views

How to deal with an additive constant in a linear congruence equation?

I am trying to solve the following equation: $10x+3 \equiv 2 \pmod{17}$. The problem I am having is that I don't know what to do with the number $3$. This is what I have done so far: $10x+3 = ...
0
votes
3answers
36 views

Help solving congruence equation (modulo).

If $x \in \mathbb{Z}$ and we have $14x +3 \equiv 5x - 6 \pmod 8$ $(5x+1)^2 + 2 \equiv 3 \pmod 6$ How do I find the solution set for $x$?
1
vote
3answers
63 views

Sum of possible all possible $x$ such that $51 \equiv 3 \pmod{x}$

I was asked this simple following question: What is the sum of all positive integers $x$ such that : $$51\equiv 3 \pmod{x}$$ My answer is $118$ (and I am pretty sure it's right but would like ...
2
votes
2answers
35 views

Perfect square is $0$ or $1$ modulo $4$ . [closed]

Prove that for every integer $n$ either $n^2 \equiv 0\pmod{4}$ or $n^2\equiv 1\pmod{4}$
3
votes
4answers
102 views

Congruences and prime numbers

I was first asked to show that a product of numbers of the form $4k+1$ also has this form. I got stuck on the next part: Deduce that if $n \equiv −1 \pmod 4$ and $n > 0$ then $n$ must have a prime ...
2
votes
0answers
65 views

Paper of Paul Erdös

I'm trying to understand On Arithmetical Properties of Lambert Series by Erdös, but am stuck on the first page. He states: Put $k=\left[(\log n)^{1/10}\right]$ and let $p_1,p_2,\ldots$ be the ...
0
votes
2answers
35 views

Prove that $5a^2 \equiv k \bmod 12$ where $k \in \{0,5,8,9\}$.

Prove that $5a^2 \equiv k \bmod {12}$ where $k \in \{0,5,8,9\}$. Hence show that the equation $24x^7 + 5y^2 = 15$ has no integer solutions. I think I need to evaluate each case with the $k$ ...
1
vote
2answers
25 views

Let $m$ be the smallest positive integer such that $a^m \equiv 1 \pmod n$

Let $n \in \mathbb{N}$, $a$ an integer and $\gcd(a, n) = 1$. Further, let $m$ be the smallest positive integer such that $$a^m \equiv 1 \pmod n.$$ Prove that $m$ divides $\phi(n)$. Can anyone help ...
1
vote
1answer
31 views

Euler's theorem for congruences [closed]

Using Euler's theorem, how to compute: a) $3^{1000} \pmod{2500}$ b) $7^{1001} \pmod{2500}$ c) $101^{21600} \pmod{81000}$
1
vote
2answers
42 views

Elementary theory of numbers and congruences

How to find solutions for: $x^2\equiv 8\pmod{ 3}$ $x^2\equiv 15\pmod{ 31}$ $x^2\equiv 54\pmod{ 7}$ $x^2\equiv625\pmod{9973}$
3
votes
3answers
108 views

Solve the congruence $3x^2+x+8\equiv 0 \pmod{11}$

How to find the solutions of this congruence? $$3x^2+x+8\equiv 0 \pmod{11}$$ I need to find the inverse of $3$, and there I have a problem.
1
vote
2answers
25 views

How can I apply the Chinese Remainder Theorem when a modulus is the square of another one?

For example: $$\begin{cases} x = 23 \mod 3 \\ x = 8 \mod 9 \\ x = 33 \mod 4 \end{cases}$$ I know that when two moduli are not mutually prime (for example: $$\begin{cases} x = n \mod 45 \\ x = m \mod ...
2
votes
1answer
45 views

How to get all solutions of $x^2 \equiv$ $a$ mod $p$?

So I'm trying to find all solutions of $x^2 \equiv$ $a$ mod $p$ and for some reason the formulas that are suggested everywhere online (for example, here) say that, if p is an odd prime and you have a ...
2
votes
0answers
69 views

Solve the congruence relations for x

I have the following two congruence relations: (1) $x^3\equiv 156417\pmod {262063}$ (2) $(7x+19)^3\equiv 6125\pmod {262063}$ And I need to solve this for x. I changed equation (2) into the ...
1
vote
1answer
27 views

What is a supercongruence?

I am very familiar to the congruences in modular arithemtic, But sometimes I can see questions related to supercongruences but I couldn't find any information about it on google. Can someone explain ...
0
votes
1answer
16 views

Modular Inverse of a given Equation

Am having a problem trying to quickly spot the inverse of any modulo system of equations. This is that i had in mind... if i for example had $35^{-1}\pmod 3$, the answer if 2. How we arrive to 2 is i ...
2
votes
1answer
53 views

Supercongruence for Binomial Coefficients

$${p^{e+1} \choose p\cdot k } \equiv {p^{e} \choose k } \mod p^{e+1} $$ $p$ is prime, $e$ and $k$ are non negative integers. I am struggling with a proof of the above proposition, in the ...
0
votes
1answer
29 views

To solve following system of equivalences of integers

To solve following system of equivalences of integers $x \equiv 2 \pmod {15}$ $x \equiv 4 \pmod {21}$ The number of solutions in x, where $1\leq x\leq 315$ is A. 0 B. 1 C. 2 D. 3 So i have to ...
2
votes
0answers
52 views

Solve the congruence system

I'm asked to solve the following congruence system: $$ \begin{split} x &\equiv 2 \pmod{5}\\ 2x &\equiv 1 \pmod{7}\\ 3x + y &\equiv 4 \pmod{11} \end{split} $$ But I think that by ...
2
votes
3answers
31 views

If $m$ and $a$ are co-prime positive integers then show that $ax \equiv b \pmod m$ has a solution, and any two solutions differ by a multiple of m.

If $m$ and $a$ are co-prime positive integers then show that $ax \equiv b \pmod m$ has a solution, and any two solutions differ by a multiple of m. I begun by using the definition of co-prime ...
3
votes
5answers
90 views

What will be the remainder when $2^{31}$ is divided by $5$?

The question is given in the title- Find the remainder when $2^{31}$ is divided by $5$. My friend explained me this way- $2^2$ gives $-1$ remainder. So,any power of $2^2$ will give $-1$ ...
0
votes
1answer
47 views

Solve in set of natural numbers

Solve in set of natural numbers the following systems: \begin{align} &\text{(a)} && x + y = 150,\quad \gcd(x, y) = 30\\[12px] &\text{(b)} && \gcd(x, y) = 45,\quad 7x = ...
2
votes
1answer
104 views

Leibniz theorem : A natural number $p> 2$ is prime iff $(p - 2)!-1 \equiv 0 \pmod p$.

I thought of using Wilson's theorem for the proof. First we have by Wilson's theorem $$(p - 1)!+1 \equiv 0 \pmod p$$ We can write this as $$(p - 2)!(p-1)+1 \equiv 0 \pmod p$$ $$(p - ...