For question about the properties or calculation of congruences and congruences equation, and related theorems of congruences like chinese remainder theorem, Fermat's little theorem and Euler's totient theorem.

learn more… | top users | synonyms

1
vote
1answer
22 views

Verification of binomial coefficient congruence $\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$

Let $j\ge 1$ be an integer and $p$ prime. Is it true that $$\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$$ My work No, take $j>p$, then the RHS is zero, while the LHS need not be $\equiv 0$. For ...
1
vote
3answers
39 views

If $x$ leaves remainder $2$ when divided by $8$, what will the remainder be when $x + 9$ is divided by $8$?

If the positive integer $x$ leaves a remainder of $2$ when divided by $8$, what will the remainder be when $x + 9$ is divided by $8$? I love to put stuff into algebraic equations to make life ...
0
votes
0answers
22 views

is binomial congruence given in article true or false?

I'm just reading a paper which, on its page 3, Application 8, claims the following: $$\binom{k+sp}{j}\equiv\binom{k}{j}\pmod{p}$$ where $p\ge 1$, $s\ge 1$, $k\ge 1$ and $p\not\mid j$ (actually, it ...
0
votes
1answer
26 views

The number of ways to form $1110€$ using $45$ notes of $20€$ and $18$ notes of $50€$

Let 45 notes of 20€ and 18 notes of 50€, how many different forms we can have 1110€? I don't know write the congruence, I had thought the following: $$45 x \equiv 1110 \pmod{20}$$ $$18 x \equiv ...
0
votes
2answers
40 views

Count the integers between $20000$ and $30000$ that end in $39$, and end in $33$ in base $4$, and end in $37$ in base $8$

How I can calculate the integers between $20000$ and $30000$ that end in $39$, and end in $33$ in base $4$, and end in $37$ in base $8$. I think that I have to solve the system of congruences: ...
0
votes
1answer
36 views

Modular arithmetic and linear congruences

Assuming a linear congruence: $ax\equiv b \pmod m$ It's safe to say that one solution would be: $x\equiv ba^{-1} \pmod m$ Now, the first condition i memorized for a number $a$ to have an ...
-2
votes
0answers
34 views

Let $m \in \mathbb{N}$. Prove that the congruence modulo $m$ relation on $\mathbb{Z}$ is transitive. [closed]

Let $m \in \mathbb N$. Prove that the congruence modulo $m$ relation on $\mathbb Z$ is transitive. How would you go about doing this?
1
vote
4answers
44 views

$ab\equiv 1\pmod{m} \implies a^q\not\equiv 0\pmod{m}$?

Let $a,b,q,m$ positive integers. Assume that $ab\equiv 1\pmod{m}$. Is it true that $a^q\not\equiv 0\pmod{m}$? My approach: If $a^q\equiv 0\pmod{m}$, then $a^qb\equiv 0\pmod{m}$ and so $0\equiv ...
0
votes
1answer
43 views

Under what conditions can we obtain $a \equiv 1 \pmod{mn}$ from $a \equiv b \pmod{m}$ and $b \equiv 1 \pmod{mn}$?

If $a \equiv b \pmod{m}$ and $b \equiv 1 \pmod{mn}$, are there any conditions under which we can conclude that $a \equiv 1 \pmod{mn}$? Here $m$ and $n$ are any integers; $a$ and $b$ are both coprime ...
2
votes
1answer
30 views

Finding the lowest number (or an upper bound to the lowest number) not congruent to a set of moduli

Note: if finding x is not possible, an upper bound, where there must be at least one number less than said number which is not congruent to the set, would be helpful. The set: For my purposes, the ...
0
votes
3answers
87 views

prove transitivity property congruence mod m

Prove transitivity property of congruence mod m. Show that if $x\equiv y \pmod m$ and $y \equiv z\pmod m$ then $x\equiv z\pmod m$ . I didn't really get the tutors explanation of this, I get what ...
2
votes
3answers
95 views

Solution of equation $ x^2\equiv 1 \pmod{784}$

How to solve the equation $ x^2\equiv 1 \pmod{784}$ ? Context I know the Chinese Remainder theorem, but have no idea how to begin. Could you give me any clue? The only thing that I would like to is ...
3
votes
0answers
29 views

Predicting the Order of Quadratic Residues

Using Euler's criterion we can tell if an integer is a quadratic residue modulo a prime. For example, if the prime was 11, then we could test the integers from 1 to 10 and determine that 1, 3, 4, 5, ...
2
votes
1answer
43 views

Problem about Eisenstein series on $\Gamma_1(N)$

I'm learning about Eisenstein series on $\Gamma_1(N)$ and it seems to me that I have misunderstood something. I imagine the following situation : Let $\nu$ be a function on $(\mathbb{Z}/ N ...
1
vote
0answers
63 views

An integer a is over 37, remainder is two unit smaller than the square of the quotient.

An integer $a$ is over $37$, remainder is two unit smaller than the square of the quotient. We want to know the maximum value of $a$ is divisible by which one of the following numbers? a.$9$ b.$12$ ...
0
votes
2answers
35 views

Can we say If q is incongruent to p modulo n then $q\equiv -p$ (mod n)

Am I right to write: If q is incongruent to p modulo n, then $q\equiv -p$ (mod n) Thanks for helping
0
votes
0answers
32 views

Prove that $l = k/\gcd(m,k)$.

Suppose $ml = kt$ where $t$ is an integer and $m<k.$ $\implies k~|~ml$ $~~~~~$and $~~~~~$ $1 \leq \gcd(m,k) \leq m$ $\implies \dfrac{k}{\gcd(m,k)}~\Big|~\left(\dfrac{m}{\gcd(m,k)}\right)l$ ...
-1
votes
1answer
30 views

How to solve system of congruence?

I think about solution to this system of congruence. Could you give me a clue ?
3
votes
7answers
58 views

Suppose that $m \ge 0$ show that $49 \mid 5\cdot3^{4m + 2} + 53\cdot2^{5m}$

I've re-written the equation in a few different ways hoping for a few different approaches: $$49y = 5 \cdot 3^{4m + 2} + 53 \cdot 2^{5m} $$ I think the first equation has more potential, since it ...
0
votes
1answer
42 views

Having trouble with Chinese Remainder Theorem

I am having trouble with the Chinese Remainder Theorem. For this question..the equation $5x\equiv 3 \pmod6$ I found there is exactly one incongruent solution modulo $6$. But then I found 3 solutions ...
3
votes
2answers
245 views

Chinese remainder problem

$\begin{cases} x \equiv 39 \pmod{189}\\ x \equiv 25 \pmod{539}\\ x \equiv 39 \pmod{1089}\end{cases}$ but two moduli are not pairwise prime $(189, 1089)=3$ What do we do to solve it then? Should we ...
0
votes
2answers
22 views

Proof: Every normal subgroup has corresponding Congruence relation and vice versa

I am trying to prove the claim in the title. I was able to do most of the work, but I still need some help. I will show what I have written so far, and will highlight the parts in the proof that I ...
1
vote
4answers
94 views

Modular Arithmatic - Solving congruences

I'm sure this is pretty basic but I'm struggling to understand how to go about solving this problem for my homework. The question states "Solve the following congruences for x". The first problem is ...
0
votes
3answers
50 views

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 ...
4
votes
2answers
45 views

Solving congruences

I've the following congruence system: \begin{align*} I \quad 2x \equiv 0\mod 7 \\ II \quad x \equiv 1 \mod 5\\ III \quad x \equiv 3 \mod 4 \end{align*} Now I tried to solve it: \begin{align*} II ...
3
votes
4answers
55 views

What is the interpretation of $a \equiv b$ mod $H$ in group theory?

I.N. Herstein has defined: Let $G$ be a group, $H$ a subgroup of $G$; for $a,b \in G$ we say $a$ is congruent to $b \mod H$, written as $a \equiv b \mod H$ if $ab^{-1} \in H$. Let $G$ be a ...
1
vote
8answers
169 views

How to solve this congruence $17x \equiv 1 \pmod{23}$?

Given $17x \equiv 1 \pmod{23}$ How to solve this linear congruence? All hints are welcome. edit: I know the euclidean Algorithm and know how to solve the equation 17m+23n=1 but I dont now how to ...
0
votes
0answers
11 views

Covering Systems library

I'm looking for examples of exactly m-covering systems (for different ms) of congruences. Is there such a library or any resource that can list some ?
1
vote
0answers
19 views

Determining the number of solutions of the equation $y^2 = x^3 + x^2 + 5$ in $\mathbb{Z}/p^k \mathbb{Z}$ in function of $k$.

I found a question that asked me to discuss the number of solutions of the equation $y^2 = x^3 + x^2 + 5$ in $\mathbb{Z}/p^k \mathbb{Z}$ in function of $k$. I would like to use the multivariate ...
0
votes
1answer
7 views

contextual system of congruences

A large wholesale company for books uses three different types of shelf in their ware- houses. Their capacity is gauged in terms of a certain specimen book of average size, known under the nickname ...
0
votes
1answer
26 views

$p$ is an odd prime and $a\in\mathbb{Z}$ with $\gcd (a,p)=1$ implies $\exists x\in\mathbb{Z}:x^2\equiv a\bmod p$ iff $a^\frac{p-1}{2}\equiv 1\mod p$

Let $p$ denote an odd prime and let $a\in\mathbb{Z}$ with $\gcd(a,p)=1$. I want to show that it holds $$\exists x\in\mathbb{Z}:x^2\equiv a\text{ mod }p\;\;\;\Leftrightarrow\;\;\;a^\frac{p-1}{2}\equiv ...
2
votes
3answers
100 views

How do you prove that $ n^5$ is congruent to $ n$ mod 10? [duplicate]

How do you prove that $n^5 \equiv n\pmod {10}$ Hint given was- Fermat little theorem. Kindly help me out. This is applicable to all positive integers $n$
1
vote
1answer
56 views

Number of solutions of some congruence equations.

How many $[u]\in(\mathbf{Z}/ab\mathbf{Z})^\ast$ satisfy the equations $u\equiv 1 \bmod \ a$, $u\equiv 1 \bmod \ b$? I somehow believe that the answer might be $(a,b)$. Is this actually true? Is the ...
0
votes
5answers
44 views

Diophantine Equation (Hint or Help)

Solve the equation below: $19x+29y=1000$ My try: $19x=1000-29y \rightarrow x=\frac {1000-29y}{19} , x \in N \rightarrow 1000-29y\equiv 0\pmod {19} \rightarrow 29y\equiv 1000\pmod{19} \rightarrow ...
2
votes
3answers
62 views

How to use Legendre symbol to find a prime which divides $ax^2+b$?

I'm trying to prove that $\dfrac{x^2-2}{2y^2+3}$is never an integer if $x,y\in\mathbb{Z}$. It can be proven if $\forall p\in\mathbb{P}\:$doesn't suffice both of the following congruences: $$\: ...
3
votes
1answer
274 views

Proving $n^{97}\equiv n\text{ mod }4501770$

How do we show $$n^{97}\equiv n\text{ mod }4501770$$ for all integer $n$? First of all, I thought I could use Fermat's little theorem or Euler's theorem, but I'm not sure if they are applicable here.
0
votes
4answers
56 views

$a \equiv b \pmod n$ and $c\equiv d \pmod n$ implies $ac \equiv bd \pmod n$

Given that $a \equiv b \pmod n$ and $c\equiv d \pmod n$, I need to prove that $ac \equiv bd \pmod n$ So far, I've only managed to deduce that $a+b \equiv c+d \pmod n$. I don't know if this is usable, ...
1
vote
2answers
26 views

Congruency by completing the square

$x^2+x+1\equiv 0\mod 49$ We have the ring isomorphism $\mathbb{Z}/49\mathbb{Z}\to\mathbb{Z}/7\mathbb{Z}\times\mathbb{Z}/7\mathbb{Z}$. Consider $x^2+x+1\equiv 0\mod 7$ I usually solve these ...
1
vote
2answers
66 views

Solving congruency

$x^2+1\equiv 0 \mod 99$ I rearranged the congruency to get $x^2\equiv -1 \mod 99$. We have an isomorphism $\mathbb{Z}/99\mathbb{Z}\to\mathbb{Z}/ 3 ...
1
vote
0answers
23 views

prove this Congruent equation

The question is: if p is prime and odd number, prove that: $1^{p-1} + 2^{p-1} +\ ... \ + (p-1)^{p-1} \equiv p + (p-1)! \ (mod\ p^2)$ I have no idea about this. I was trying to use Wilson but no ...
1
vote
1answer
38 views

Congruent Equation Prove

I was trying to prove this equation I did these but I don't know what to do next?! $2^a-1\equiv 2^{a\ \bmod\ b}-1 \ \bmod\ (2^b -1)$ My solution: $$ a = cb+r$$ $$ 2^{cb+r} \equiv 2^r (\bmod \ 2^b ...
0
votes
2answers
40 views

How to solve this quadratic congruence equation?

Well, we have : $$n^2+n+2+5^{4n+1}\equiv0\pmod{13}$$ i'm little bit confused, I think i can solve this using the reminders of $n^2$, $n$ and $5^{4n+1}$ over $13$, by the way I have no idea about the ...
0
votes
3answers
40 views

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 ?
-1
votes
1answer
28 views

Congruents and modulo question- counterexample

I have tired an couple and none seem to be working
2
votes
1answer
35 views

Techniques in solving the congruence modulo

How can the congruence ${x}^{17389}\equiv43927 \pmod{64349}$ be solved? I read that the first step is to solve the congruence $17389d\equiv1 \pmod{63840}$. I think $d$ is a number such that $17289d≡1 ...
2
votes
4answers
65 views

$x^n =2($mod $13)$

Consider the congruence $x^n =2($mod $13)$. Then for which n does it have a solution? n= 5 n=6 n=7 n=8 Can we take any help from this fact $x^{12 }=1 ($ mod $13),\forall x $? Please give some ...
2
votes
2answers
57 views

Does there exist any integer $ n> 1$ for which $6^{2n}-25$ is prime?

I got this question on a test and I am really curious hoe you would approach it. I tried to prove stuff using the congruence laws but I didn't manage to prove anything.
1
vote
2answers
42 views

Property of modulo division

I wanted to check if it is true, that $$a^{3b} \pmod n = (a^{b} \pmod n)^{3}\ ?$$ For example when $a = 2, b = 4, n = 5$ I have that $2^{12} \mod 5 = 1$ and $(2^4 \mod 5)^3 = 1$ Is that always true, ...
0
votes
2answers
38 views

Property of Modular arithmetic

If I know that $$g^a \neq 1 \mod b$$ is that always true that if I will take a positive integer $c$ and count $(g^a)^c$, then $$(g^a)^c \neq 1 \mod b$$?
1
vote
2answers
37 views

Solve congruence with primitive root

I am seeking the solution to the congruence $$ 29x^{33} \equiv 27\ \text{(mod 11)} $$ Primitive root is 2 and $ord_{11} (2) =10$. Then I got so the equation can be field: $$ lnd_2(29) + 33 ...