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
2answers
42 views

Extending Euler's Theorem gives minus 1 - why?

Euler's Theorem states that for some coprimes $n$ and $a$: $a^{\phi(n)} \equiv 1 \mod n$ Example: $ a = 10, p=7, q=11, n=p*q=77, \phi(n) =(p-1)*(q-1)= 60$ $10^{60} \equiv 1 \mod 77$ When I take ...
1
vote
0answers
36 views

How to prove taht a product of two complete residue system is not a complete residue system?

Claim. Let $n$ be a natural number and $A=\{0,1,2,3,\cdots,n-1\}$ be a complete set of residues modulo $n$. Let $\sigma$ be a permutation of $A$. Show that the set $C=\{\sigma(i)i:i\in A\}$ is not a ...
3
votes
1answer
50 views

Integer $m$ such that $2^m\equiv\pm 1\pmod{2n+1}$

Let $n$ be a positive integer. Does there always exist a positive integer $m\leq n$ such that $2^m\equiv\pm 1\pmod{2n+1}$? It is true that $2^{\phi({2n+1})}\equiv 1\pmod{2n+1}$. If $2n+1$ is prime, ...
1
vote
1answer
24 views

Congruence with $x$ in a power

I don't know how to find $x$ in a situation like this: $$a^x \equiv b \pmod c$$ I think I'm missing something around little fermat theorem, Could anyone help?
1
vote
2answers
39 views

How to prove $x^{\phi(m)+1}\equiv x\pmod{p}$ [duplicate]

How do I prove that $x^{\phi(m)+1}\equiv x\pmod{p}$ when $m=pq$, two distinct primes? I kind of have an idea that it involves Euler's Theorem but it doesn't seem to be working as well as I wanted it ...
2
votes
3answers
53 views

Is there a number congruent to 1 modulo infinitely many primes?

Let $A=\left\{ p_{r},p_{r+1},\dots\right\}$ a (infinte) set of consecutive prime numbers (if you prefer, if $\mathfrak{P}$ is the set of all prime numbers, $A=\mathfrak{P}-\left\{ ...
1
vote
2answers
46 views

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod {73}$

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod{73}$. It is clear that an attempt to write this out as $90x-41=73n,\exists n\in \mathbb{Z}$ won't be very ...
2
votes
1answer
21 views

A possible defining characteristic of primitive roots.

If $n$ is a primitive root $\bmod p$ ($p$ is an odd prime ) does there always exist a least residue $t$ such that $n^t \equiv t \pmod p$ ?
0
votes
1answer
25 views

How to find $x$ in $\left\lfloor{\frac{x-2000}{4}}\right\rfloor+x\equiv0\pmod 7$

Find all integers $x$ such that $2000\leq x\leq2100$ and $$\left\lfloor{\frac{x-2000}{4}}\right\rfloor+x\equiv0\pmod 7$$ Please, I have no idea how to proceed... any help is really appreciated
0
votes
0answers
29 views

How to prove a congruent to b (mod n) is a bijection?

I can prove it's an equivalence relation, but NO idea how to prove it's a bijection. I know I need to prove it's surjective/injective, but how do I establish it to even be a function?
6
votes
1answer
122 views

Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align} This number is a 100-digit prime ...
2
votes
2answers
27 views

How to solve this congruence?

Given that $6^{12} ≡ 16\pmod {109}$. Is there a $k$ such that $16^k ≡ 6 \pmod {109}$? If there is, then find all the $k$'s. Does anyone know how to do this? Thanks
3
votes
0answers
39 views

Trying to prove a congruence for Stirling numbers of the second kind

I am struggling with a demonstration for this: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace ...
1
vote
1answer
53 views

Find the residue of $1!+2!+…+n! \pmod{m}$ for $m>n$

Find the residue of $ 1!+2!+........+n! \pmod{m}$ for $m>n$ $n,m$ are positive numbers and need not be primes. is there any known proof or result for this thanks
0
votes
3answers
19 views

Congruences - proof problems

1) State what is meant by $a\equiv b \pmod n$. 2) Suppose that $a\equiv b \pmod n$ and $c\equiv d \pmod n$. Prove that i) $a+c\equiv b+d \pmod n$ ii) $ac\equiv bd \pmod n$ For question 1, ...
1
vote
1answer
41 views

Solving $x^n \equiv a \text{ (mod } p)$ in $\mathbb{Z}$

I want to show that for any integers $a$ and $n,$ ($n > 1$) there are infinitely many primes $p$ such that $$x^n \equiv a \text{ (mod } p).$$ When $n$ is odd, I used the fact that if $(a,p)=1$ ...
0
votes
1answer
18 views

System of congruences with not coprime numbers

I have a system of congruences, for example $ x \equiv 2 \mod 15$ $ x \equiv a \mod 21$ where $a$ is an integer to be determined. I have to find all the values of $a$ for which the system has ...
0
votes
0answers
17 views

Is it possible to get nontrivial $n$ such that we can find BOTH $n \pmod p$ and $\log{(n)} \pmod p$?

If we are looking for a value $n \equiv v \pmod p$ or $n \equiv v_r + v_i i \pmod p$, where $v_r+v_i\cdot i$ is a complex number modulo $p$, is it ever possible to have a situation where we can find ...
0
votes
0answers
20 views

congruence, please hepl me solve this

$$ x^4 + x + 3 = 0 \pmod{3^3} $$ I'm not sure how to this, I've tried many times but it never works for me :/ so, I hope someone will help me
1
vote
4answers
48 views

Prove or disprove: there is an integer $x$ so that $x \equiv 2$ (mod 6) and $x \equiv 3$ (mod 9).

Prove or disprove: there is an integer $x$ so that $x \equiv 2$ (mod 6) and $x \equiv 3$ (mod 9). I'm not too sure how to approach this. I first noted that $(6,9) = 3 \neq 1$ so I cannot use ...
2
votes
3answers
31 views

Solutions for a system of congruence equations

I have a system $$ \begin{cases} x \equiv 7 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ How can I show that the system does not have any solutions? I know that the first implies that $x = ...
1
vote
2answers
50 views

How to solve $x^2 \equiv [1]$ in $\Bbb Z_5$

I would like to know how to solve $x^2 \equiv [1]\text{ in }\Bbb Z_5$? How to solve this kind of equation in general?
0
votes
2answers
24 views

Getting the General Solution of Linear Congruence

$4x \equiv 12 \pmod {26}$ I have this equation and I understand that it has two solution via $\text{gcd}(26, 4)$. One of the answers is $x\equiv3$, which I can get by multiplying both sides by ...
3
votes
2answers
50 views

The inverse of $4$ modulo $9$

Can someone explain why the inverse $4$ modulo $9$ is $7$? What am I missing? $$9 = 2\cdot4 + 1$$ $$1 = 9-4\cdot2$$ $$1 = -2\cdot4 + 1\cdot9$$ Isn't then $-2$ inverse of $4$ modulo $9$?
0
votes
1answer
17 views

Question - Corresponding parts of congruent triangles

Please answer the question below with these specifications: If the answer is yes write a paragraph proof to show which congruence shortcut utilized. Show all rules of geometry that are applied to ...
0
votes
1answer
33 views

Linear congruence solution confusion

Why does: $4x \equiv 2 \bmod 6 $ have the solutions: $x \equiv 2 \bmod 6 $ AND $x \equiv 5 \bmod 6 $ I understand why $x \equiv 2 \bmod 6 $ as: $4 \cdot 2 = 8$ which is $2 + (1 \cdot 6)$ :. ...
3
votes
4answers
160 views

System of congruence equations

I have a system of congruence eqs $$ \begin{cases} x \equiv 14 \pmod{98} \\ x \equiv 1 \pmod{28} \end{cases} $$ I have calculated $\text{gcd}(98,28) = 14$. I can from the congruence eqs get $x = ...
0
votes
1answer
24 views

Z / 6Z being a set of well dedfined equivalence classes, and a congruent to b(mod 6)

why is this = [0],[1],[2],[3],[4],[5],[6] and how would I define f Z/6Z - Z/6Z by f([a]) = ([2a]). I have the proof but I don't understand it. Proof: Assume [a1] = [a2] in Z/6Z. then a1 congruent to ...
1
vote
2answers
73 views

Modular equations

$$ x^{13}\equiv4\pmod{101}\\x\equiv5^{5^{5^{5}}}\pmod{47\cdot27} $$ Equations are separate. How should I approach these? Both has something to do with Euler's theorem, I believe, but all my attempts ...
0
votes
3answers
30 views

Does a system om congruence equations have solutions?

I have a system of congruence equations $$ \begin{cases} x \equiv 17 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ I need to investigate the system and see if they've got any solutions. I know ...
1
vote
1answer
26 views

How can I solve these congruences?

I have no idea, how to solve these congruences if you can help me please. Thanks a lot.
0
votes
2answers
44 views

How do I solve simultaneous congruence modulo equations

How do I find one value of $x$ in these equations? $$ \begin{cases} x \equiv 3 \pmod{5}\\ x \equiv 4 \pmod{7} \end{cases} $$
1
vote
1answer
29 views

Solutions of $a^{2} - 2b^{2} \equiv 0$ mod $p$

I came across this question in attempting to find $p$ for which $\mathbb{Z}_{p}[\sqrt{2}]$ is a field. Consider the equation: $$a^2 - 2b^2 \equiv 0 \enspace \text{mod p}$$ For which primes $p$ is ...
5
votes
2answers
849 views

Why is $20 ≡ 2 \pmod 6\;?$

Could anyone explain to me why $20 ≡ -22 \pmod 6\;?$ At school we did the following method to find $-x \mod n$ by doing: $x \mod n$ (in this case $22 \mod 6 = 4)$ $n - r$ (in this case $6-4 = ...
-3
votes
2answers
40 views

How to show $a c\equiv bc\pmod{n}$ where $n \ge 2$ does not imply $a \equiv b \pmod n$? [closed]

How to show $a c\equiv bc\pmod{n}$ where $n \ge 2$ does not imply $a \equiv b \pmod n$? Would it be possible for someone to go over this step by step?
0
votes
2answers
20 views

Modulo congruence

I have a problem here that I have no idea how to go about solving. It states: Let $n∈Z$ with $n>1$. (a) If $n=2k$ for some odd integer $k$, prove that $k^3≡k \pmod{2n}$. (b) If $n=2k$ for ...
0
votes
2answers
19 views

$\gcd(a,n)=d$ and $s,t$ solutions to $ax\equiv b \pmod{n}$ then $s\equiv t\pmod{n/d}.$

If $\gcd(a,n)=d$ and $s,t$ are each solutions to $ax\equiv b\pmod{n}$ then $s\equiv t \pmod{n/d}$. As $d\mid a$ say $a=dm$ and as $s,t$ are each solutions, $as\equiv at\pmod{n}$ so $$a(s-t)=nk ...
2
votes
1answer
21 views

Solution for congruence mod $p^2$

I've been having trouble with the following congruence, finding all primes $p$ for $$x^2 + 1 \equiv 0\ mod\ p^2$$ By the definition of quadratic reciprocity, I know that $-1$ is a quadratic residue ...
1
vote
1answer
40 views

Solve the following congruence for x (Modulo Question)

I need help in a question that I'm having a hard time understanding... It is asking to determine the congruence for $x$ and expressing the answer in the range 0-1000: $$ 200 . x = 13 \pmod{1001} $$ ...
0
votes
1answer
11 views

Congruence question, does -1 matter?

I am proving symmetry in a relation. Assume: I have $a\,R\,b$ which is $x+y\equiv z+w\pmod 2$. I want to show $b\,R\,a$ which would be $z +w\equiv x+y\pmod 2$. ("$x\mid y$" is the divides symbol.) ...
2
votes
2answers
48 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
0
votes
2answers
47 views

If $p$ is the prime of the form $4k+1$. Prove that $(1/p)+(2/p)+(3/p)+\ldots+ (P/p) = 0$

$p$ is the prime of the form $4k+1$. Prove that: $$(1/p)+(2/p)+(3/p)+\ldots+ (P/p) = 0$$ $P=(p-1)/2.$
0
votes
1answer
27 views

quadratic equation modulo some number

I read a post that $$ax^2+bx+c \equiv 1 \pmod p$$ can be solved in a similar way we solve a simple quadratic equation, just by replacing division by $2a$ by modulo inverse of $2a$ and square root of ...
2
votes
0answers
40 views

Compute digits of a number.

The question is what the last $10$ decimal digits of $2^{3^{4^{5^{6^{7^{8^9}}}}}}$ are? I do not get the following solution and its motivation. I would appreciate if someone would shed light on it. ...
4
votes
1answer
68 views

Congruence for the sums of odd powers of integers [duplicate]

Does someone know how to prove ***EDIT by induction**** that for all integers $n\ge1$, $k\gt0$ $$\sum\limits_{i=1}^{n} {i^{2k+1}}\equiv 0\ \ \ \pmod{\frac{n(n+1)}{2}}$$ I thought this should be a ...
1
vote
1answer
23 views

Some congruences and conclusion.

Let consider this situation: $$ \gcd (b, m) = 1 \tag{$*$} \\ b^a \equiv 1 \\ b^c \equiv 1 $$ Assume that $ a \le c $ Whether it is reasonable to draw a conclusion that is $c = ak$ for some $k$? Why? ...
0
votes
2answers
27 views

Operations on congruence equations?

I have to do back substitution for my homework, and I have to modify x ≡ 1 (mod 5) to x=5t+1, which I understand. What I don't understand is when I put this into the next equation which becomes 5t + 1 ...
0
votes
1answer
30 views

Equality of equivalence classes for congruence modulo 7

Let R be the relation of congruence modulo 7. Which of the following equivalence classes are equal? [35], [3], [−7], [12], [0], [−2], [17] I got 3) [35] = [-7] = [0], [3] = [17], [12] = [-2] ...
1
vote
1answer
25 views

Factorial Divides Rising Power Proof Help

I'm trying to prove the following: $m^{\overline n} \equiv 0 \bmod n!$ Where $m^{\overline n} = m\left({m+1}\right)\left({m+2}\right)\ldots\left({m+n-1}\right)$, the product of $n$ successive ...
0
votes
2answers
35 views

What steps are needed to solve $5x+80 = 13 \pmod 7$ and similar problems?

I am unsure of the steps needed to solve $$5x+80 = 13 \pmod 7$$ or this, $$31x=2\pmod{19}$$ I would like to see the steps necessary.