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

0
votes
2answers
32 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
31 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$ ...
0
votes
1answer
27 views

How to solve system of congruence?

I think about solution to this system of congruence. Could you give me a clue ?
1
vote
0answers
65 views

How to solve this elementary counting problem? [closed]

Prove that, for every positive integer $k$, the following sets have the same cardinality: $$ \{(a,b)\in\mathbb Z^2: 0<b<a<k, \quad 7(a+3b)\equiv k-2b\pmod{49}\}, $$ $$ \{(a,b)\in\mathbb Z^2: ...
3
votes
7answers
57 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
40 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
243 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
81 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
45 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
43 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
54 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 ...
2
votes
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
25 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
98 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
55 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
42 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
58 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
175 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
65 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
22 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
33 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
60 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
34 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 ...
21
votes
11answers
2k views

Shall remainder always be positive?

My cousin in grade 10, was told by his teacher that remainders are never negative. In a specific example, $$-48\mod{5} = 2$$ I kinda agree. But my grandpa insists that $$-48 \mod{5} = -3$$ Which ...
2
votes
4answers
253 views

Find number x such that $x\equiv 4^{1002}\pmod{55}$

Find a natural number x, for $0 \le x \le 54$ such that is a solution for the following equation: $$x\equiv 4^{1002}\pmod{55}$$ This question was asked in an exam, so I expect that the answer is ...
0
votes
1answer
32 views

How to show $2^{k+2}$ divides $3^{2^k}-1$ but $2^{k+3}$ doesn't?

I've got a task: Find highest power of 2 that divides $3^{2^k}-1$ so i wrote few terms and guessed that it's $2^{k+2}$, now i should show it. I tried by induction, but what i got appeals to me as a ...
0
votes
1answer
23 views

How to prove $N=13\times12v+6\times19u$ is a solution for the system?

Well, I have a system of congruences it is : $$n\equiv13\pmod{19}$$ $$n\equiv6\pmod{12}$$ I'm trying to prove that for any pair of integers $(u,v)$ the number $N=13\times12v+6\times19u$ is a solution ...
3
votes
1answer
59 views

How to show $(n-1)^3n^3(n+1)^3$ is divisible by 7 and 9?

Yeah it looks like a basic, really elementary question, but i'm having hard time with it. First i tried to show that it's divisible by 9 $$(n-1)^3n^3(n+1)^3 = ((n+1)(n-1))^3n^3 = (n^2-1)^3n^3 = ...
0
votes
1answer
24 views

Find all values of parameter A such that two system of congruences are equal

I'm starting to learn some elementary number theory and i came across a task i don't know how to solve. $$x \equiv 5 (mod \ 6)$$ $$x \equiv A (mod \ 35)$$ and the second one $$x \equiv A (mod \ ...
0
votes
2answers
46 views

Using Euclid's Algorithm prove..

Using Euclid's Algorithm prove that the fraction $\frac{24n+5}{18n+4}$ is in lowest terms. Is this solution going to be correct as a proof? Thanks for help!
1
vote
0answers
31 views

solving congruence equation system modulo prime

I need to solve a congruence system like this: $30f_0+26f_1+8f_2+38f_3+2f_4+40f_5+20f_6 \equiv 0 \pmod{41}$ $38f_0+2f_1+40f_2+20f_3+30f_4+26f_5+8f_6 \equiv 0 \pmod{41}$ ...
0
votes
2answers
67 views

Diagonalizng a bilinear form

Question a. we mark $\mathbb{R}_2[x]$ as the polynomial space of degree $ \le 2$ over the real field $\mathbb{R}$. $\xi :\mathbb{R}_2[x] \times \mathbb{R}_2[x] \to \mathbb{R}$ $$\xi(q,p) = ...
1
vote
2answers
28 views

Find all the integers that satisfy a system of congruences?

I have a doubt about systems of linear congruences: if I have solved the congruences and I have found as answers (for example) $x \cong8 \ (mod \ 12) $ and $x \cong 6 \ (mod \ 14)$, how can I find ALL ...
0
votes
1answer
19 views

Property of modulo congruation

If I have: $$a^b \equiv 1 \mod xy$$ where $x,y$ are primes, is then true that: $$ a^b \equiv 1 \mod x$$ $$ a^b \equiv 1 \mod y$$ I don't sure if this is true, because I don't know how can I prove it ...
0
votes
3answers
27 views

System of congruences?

Find all the integers $x\in \mathbb{Z}$ that satisfy the following system of equations (that is, the solution has to satisfy both equations simultaneously): $2x\equiv 1 (mod7)$ $x^{2}\equiv 1 (mod ...
3
votes
4answers
226 views

A congruence involving prime numbers

This congruence appears in a textbook I'm reading anf it left the proof to the reader, however I cannot find my way around it. $$(a+b)^ p \equiv a^p+b^p \pmod p\text{ when $p$ prime and ...
1
vote
1answer
23 views

Does any skew-symmetric matrix is congruences to a diagonal matrix?

Question Prove/disprove: if A, a matrix nxn over field F is skew-symmetric then A congruents with a diagonal matrix. My thoughts I know that any symmetric matrix whose entries are real can be ...