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
1answer
18 views

Computing Large Number Modulo and Multiplicative Inverse

Prove that $3^{28}$ is a multiplicative inverse of $9^{34}$ modulo $17$, i.e. show that $3^{28}9^{34}\equiv 1\pmod {17}$. I really have no idea how to approach this example other than applying ...
0
votes
1answer
19 views

Congruence for Stirling Number of first kind $s(n,k)$ when $n$ is prime

Let $s(n,k)$ be the Stirling numbers of first kind: $$\prod_{k=0}^{k=n-1}(x-k) =\sum_{k=0}^{k=n}s(n,k)x^k$$ $p$ is prime $\iff$ for all $k\in\{2,..,p-1\}$, $s(p,k)\equiv0\ mod\ p $ How ...
-3
votes
2answers
29 views

List the elements of a set [on hold]

Consider the universal set $N$, $$A = \{m: m\ |\ 16\}$$ and $$B = \{n: n \le 16 \text{ and } n \equiv 17 \mod 3\}.$$ List the elements of A, list the elements of B.
2
votes
2answers
50 views

How to solve $x=2^{-18}$ (mod 143)

I have to solve the following equation: $x=2^{-18} \mod 143$. The problem is that I can't use Fermat's little theorem as $\varphi(143)=120$ which doesn't help at all. The other method I know is to ...
3
votes
3answers
80 views

What is the remainder of $314^{164}$ divided by 165?

What is the remainder of $314^{164}$ divided by 165? Since 165 is not a prime, we cannot apply Fermat's Little Theorem directly. However since $165=3\times 5\times 11$, we could try to divide ...
0
votes
3answers
15 views

system of conguences

I am trying to figure out how to solve: Find $x, y \in \mathbb{Z}$ such that $$2x+y\equiv 4\pmod{17}$$ and $$5x-5y\equiv 9\pmod{17}.$$ I know this means $2x+y-4$ and $5x-5y-9$ are multiples of $17$, ...
4
votes
1answer
36 views

Find all the primes $p,q$ such that $2^{p-q}+1\equiv0\pmod{pq}$

Find all the primes $p,q$ such that $2^{p-q}+1\equiv0\pmod{pq}$ I'm not sure how to start this. I am guessing Fermat's little theorem has something to do with this as $2^p\equiv 2\pmod{p}$ and ...
1
vote
2answers
33 views

Existence of square root in $\mathbb Z_n$?

I had this question on my final exam and I struggled with it. It asks to prove or disprove the following: $$\forall m \in Z, \ \forall \ [a] \in Z_{m}, \ \exists \ [b] \in Z_{m}, [a]=[b]^{2} $$ ...
2
votes
1answer
34 views

Solve congruence using fermat's theorem [duplicate]

Hi I am given this problem and I am supposed to use fermat's theorem. Here is it is: Prove that $$24^{31} \equiv 23^{32} \pmod{19}$$ We are supposed to solve it by setting up the congruence like ...
1
vote
1answer
23 views

Prove that $z^2 \equiv ab$ mod $p$ is solvable if and only if both or neither of $x^2 \equiv b$ mod $p$ are solvable.

Suppose the $p$ is an odd prime not dividing $ab$. Prove that $z^2 \equiv ab$ mod $p$ is solvable if and only if both or neither of $x^2 \equiv b$ mod $p$ are solvable. I have no idea how to prove ...
1
vote
1answer
43 views

Congruence mod $p$

I need a proof for the following: Suppose that $p$ is an odd prime. If $(a, p) = 1$, then $x^2 = a \pmod p$ either has exactly $2$ solutions or has no solutions within $\textrm{crs}/p$. I can come ...
0
votes
0answers
44 views

Collatz algorithm generalization try-out (Collatz k-algorithm)

Recently I have been reading about the Collatz conjecture here in Mathematics Stack Exchange, and also found the fantastic paper of professor Lagarias about it. Everything was so interesting (and I ...
-4
votes
0answers
35 views

Number Theory questions [duplicate]

Let $a$ be an integer and $n$ a positive integer. Prove or provide a counter example to each of the following statements. (a) If $a$ ≡ ± 1(mod p) for all primes $p$ dividing $n$, then $a^2$ ≡ 1(mod ...
3
votes
4answers
79 views

Prove that $5 \nmid (a+1)^3 - a^3$

Prove that difference between two consecutive cubes cannot be divided by $5$. Here's what I've done, but I'm not sure about one step: Let two cubes be $(a+1)^3$, and $a^3$. $$(a+1)^3 - a^3 = ...
0
votes
1answer
29 views

Given the following, is there equivalence relation?

Let $n$ be an integer. On the set $F$ of all integer-valued functions of a set $A$, suppose we define $f$ and $g$ to be related if $f(a)\equiv g(a)\pmod{n}$ for every $a\in A$. Is this an equivalence ...
0
votes
2answers
32 views

Polynomial Congruence problem

We are asked to find the solutions to the following congruence $$ x^3 + 8x^2 - x - 1 \equiv 0 \ (\text{mod } 11). $$ I know that the solution can be computed using Hensel's Lemma or by simply using ...
0
votes
0answers
15 views

Proof solutions linear congruence

If $x_0$ is the solution of the system of linear congruence equations: $$ x \equiv c_1 \text{ mod } m_1$$ $$ x \equiv c_2 \text{ mod } m_2$$ $$ \cdots $$ $$ x \equiv c_s \text{ mod } m_s$$ AND the ...
3
votes
3answers
42 views

If $p>3$ what are two solutions of $x^2 ≡ 4 \pmod p$?

Theorem used: "Suppose that $p$ is an odd prime. If $p \nmid a$, then $x^2 ≡ a \pmod p$ has exactly two solutions or no solutions." Question: If $p>3$ what are two solutions of $x^2 ≡ 4 \pmod p$? ...
1
vote
1answer
42 views

Congruence of certain numbers mod a large prime

I have a set of small prime numbers $S = \{2,3,5,7,11,13,17,19,23,29\}$. By multiplying those I can form other numbers, by assigning to each element of the set an exponent of $0$ or $1$, so that I ...
2
votes
2answers
38 views

Simple question about modular arithmetic

I am trying to understand if I could know something about the following relationship: If I have: $b \equiv n \mod a$ $d \equiv n \mod b$ $n \gt 0$ Is it possible to know something ...
0
votes
0answers
15 views

Sorting algorithm based on the distance to the factors of the elements of the set

I am trying to understand better the basic concepts of modular-arithmetic and I was playing with a set of integers and decided to order them by using congruences, so I tried to define an algorithm to ...
0
votes
3answers
39 views

Prove or disprove the congruence

Prove or disprove the congruence below: $$15 + 111^5· (−10)\equiv 5 \pmod{11}$$ I am not sure where to start because we cannot use a calculator this problem? Can anyone guide me?
1
vote
0answers
15 views

Prove an upper bound for the multiplicative order of a congruence

This is a problem from elementary Number Theory. It's the only one I couldn't figure out and it's bothering me. Definition: Let a and n be natural numbers with (a, n) = 1. The smallest natural number ...
0
votes
2answers
37 views

Factor the polynomial $x^4 + 2x − 4$ in $\mathbb{Z}_5[x]$.

I'm confused as to how this is different from factoring in the reals? Would I start this by writing $x^4+2x-4 \equiv 0 \pmod 5$? What changes?
0
votes
0answers
39 views

Negative integers congruent modulo m [duplicate]

Prove that any negative integer is congruent modulo $m$ to exactly one of the numbers in the set $\{0,1,2,3,\dots,m-1\}$. This is how I tried to solve this. Let $a<0$. Let, $b=a+sm>=0$ where ...
3
votes
2answers
36 views

Number of elements of $\mathbb{Z}_p$ that satisfy a certain property

Let $S(n,p)=\{a\in \mathbb{Z}_p : a^n=1$ (mod $p$)$\}$ where $p\geq3$ is a prime number and $1\leq n\leq p$. I am interested in finding a general formula for cardinality of $S(n,p)$. For example, I ...
0
votes
4answers
36 views

Prove a ≡ b mod m ∧ a ≡ b mod n ⇒ a ≡ b mod lcm(m,n) (Stuck midway through solution)

I have to prove the following: $a \equiv b \mod m \wedge a \equiv b \mod n \Rightarrow a \equiv b \mod lcm(m,n)$ I already tried but I'm stuck. This is what I've got so far: $m\mid (a-b) ...
3
votes
2answers
35 views

What is $5^{11\times31}$ congruent to in modulo $11\times 13$?

My attempt: $$ 5^{11\cdot31} ≡5^{341} \pmod {143}$$ Using FLT where $$a^{p-1} ≡ 1 \pmod p$$ I get $$≡(5^{142})(5^{142})5^{57} \pmod {143}$$ $$≡5^{57} \pmod {143}$$ This is where I'm stuck.
1
vote
1answer
18 views

Solvability of quadratic congruence

Our textbook states that the solvability of a general quadratic congruence of the form $ax^2 + bx + c \equiv 0\ (\textrm{mod} \ m)$ is equivalent to solvability of the binomial congruence $x^2 \equiv ...
4
votes
2answers
53 views

Find All Solutions to System of Congruence

$$ \begin{cases} x\equiv 2 \pmod{3}\\ x\equiv 1 \pmod{4}\\ x\equiv 3 \pmod{5} \end{cases} $$ $ n_1=3\\ n_2=4\\ n_3=5\\ N=n_1 * n_2 * n_3 =60\\ m_1 = 60/3 = 20\\ m_2 = 60/4 = 15\\ m_3 = 60/5 = 12\\ ...
1
vote
0answers
24 views

Chinese remainder - Error in my solution

I have the following congruence system: $x \equiv 1 \mod 5 \\ x \equiv 2 \mod 7 \\ x \equiv 0 \mod 8 \\ x \equiv 3 \mod 11$ I used the Chinese Remainder Theorem to get a solution, but it only ...
0
votes
0answers
102 views

Why is the number of conjugacy classes modulo 16 equal to the order for a finite group of odd order? [duplicate]

Let $G$ be a group of odd order $n$ and suppose $|Con(G)| = k$ ( Con(G) is the set of conjugacy classes of G), prove that $$k \equiv n \pmod{ 16}.$$ How do I proceed on this? Thanks.
1
vote
2answers
37 views

number theory based on powers of 2

if $2^{s}$ is found by rearranging the digits of $2^r$ prove that $r=s$. I suspect that this question requires congruence but i need help.the 2 numbers have same digits, and the base 2 must have ...
0
votes
1answer
31 views

How do I prove this statement about $n^\text{th}$-power residues?

I am studying A Classical Introduction to Modern Number Theory by Ireland and Rosen, and the authors leave the proof of the following proposition (4.2.2) as "an exercise" ... Suppose that $a$ is ...
0
votes
0answers
30 views

Determining congruence with mod

I am asked to find all solutions to: $$ 5x \equiv 3\!\pmod 3$$ I have found that since $\, 3 \equiv 0\pmod 3,\ x\,$ must be a multiple of $3$. With $x = 3n.$ Is this correct?
2
votes
3answers
66 views

Prove that $1+20^1+20^2+\cdots+20^{21}\equiv 0\pmod{23}$ [closed]

How can I prove that $1+20^1+20^2+\cdots+20^{21}\equiv 0\pmod{23}$?
0
votes
0answers
44 views

Prime pairs $(p,q)$,$\quad q=(n \quad mod \quad p)$ and $2p+q=n (odd)$. Is there a definition about them?

I am studying congruences and I have observed this kind of prime pairs $(p,q)$ related to odd numbers. Do this kind of prime pairs have a name or have been studied before? Here is the definition: ...
0
votes
2answers
30 views

Solution system $3x \equiv 6\,\textrm{mod}\,\, 12$, $2x \equiv 5\,\textrm{mod}\,\, 7$ , $3x \equiv 1\,\textrm{mod}\,\, 5$

Have solution the following congruence system? $$\begin{array}{ccl} 3x & \equiv & 6\,\textrm{mod}\,\, 12\\ 2x & \equiv & 5\,\textrm{mod}\,\, 7\\ 3x & \equiv & ...
3
votes
1answer
36 views

Find equivalence classes of x ~ y : <=> x-y ∈ Z

The equivalence relation is: $$X=\mathbb{R}$$ $$x∼y:⇔x−y∈\mathbb{Z}$$ I proved the relation properties but how can I find the equivalence classes? Also I was wondering whether the equivalence ...
0
votes
1answer
155 views

Proof of Lallement’s Lemma

i am a bit weak with my congruence manipulation when it comes to semigroup theory. Could you possibly check my proof and give me constructive criticism on it? Lemma: Let $S$ be a regular semigroup ...
3
votes
3answers
164 views

Prove the following using the Wilson's Theorem

Given a prime number, $p$, prove that $(p-1)!\equiv p-1\,\,\left(\text{mod }\frac{p(p-1)}2\right)$ How do we modify the Wilson's theorem into modulo $p(p-1)/2$ ? I can't get any clue (original ...
3
votes
2answers
41 views

Solutions of the quadratic congruence $x^2\equiv 35\pmod{67}$

What are the solutions of the following quadratic congruence? $$x^2\equiv 35\pmod{67}$$ I can prove that the congruence has a solution but I can't find the solutions.
0
votes
2answers
33 views

Consider the system of Congruences $x \equiv a \pmod{m}$ and $x \equiv b \pmod{n}$

I want to prove that this system has a unique solution $\pmod{\frac{mn}{g}}$, where $g= \gcd(m,n)$ provided that $g \mid b-a$ Here is my attempt. From $x \equiv a \pmod{m}$ we know that $m \mid ...
3
votes
1answer
39 views

All the solvable congruences $x^2 \equiv a \pmod n$ have the same number of solutions

Prove that for a fixed integer $n >1$, all the solvable congruences $x^2 \equiv a \pmod n$ with $ \gcd(a, n) = 1$ have the same number of solutions. My try: Let a solution be $x_0$ and let ...
4
votes
1answer
41 views

Prove that $2^{4n}+1$ cannot be a prime if $3|n$

$2^{4n}+1$ cannot be a prime if $3|n$ and $n>0$ My Try: $$2^{12k}+1\equiv (-1)^{3k}+1 \equiv0\pmod{17}$$ So it divisible by $17$ for odd $k$. But how to complete the proof?
1
vote
1answer
21 views

Solving a second degree congruence relation

Suppose $n = pq$ where $p$ and $q$ are distinct odd primes. Let $r$ be an integer such that $r \equiv p^{-1} \pmod q$, and put $s = 1 − 2rp$. Let a be an integer such that $(a, n) = 1$.Show that the ...
0
votes
0answers
22 views

Show that if Eve intercepts C and B, she can find the message M

Suppose Alice and Bob are both using RSA with public encryption keys (e1, n) and (e2, n) respectively where eA and eB are coprime. Charles encrypts the message M, where gcd(M, n) = 1, with Alice and ...
0
votes
2answers
29 views

Showing that $x \equiv a \pmod m$ and $x \equiv b \pmod n$ ha s unique solution mod $mn/(m,n)$

I have the following system of congruences $$\begin{align} x &= a \pmod m \\ x &= b \pmod n. \end{align}$$ I need to prove that this system has unique solution mod $mn/d$ where $d = ...
8
votes
4answers
121 views

Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.

I'm not sure if it's correct, but what I have so far is; $$21n^5 + 10n^3 + 14n ≡ (1 + 0 - 1) ≡ 0 \mod 5$$ but I'm having trouble solving it in $\bmod 3$. I have: $$21n^5 + 10n^3 + 14n ≡ (0 + (?) + ...
0
votes
0answers
27 views

What is the error with these congruence equation?

Suppose I was trying to give some $x \in \mathbb{Z}$ such that $3x \equiv 5 \mod 7$ then multiplying by $12$ gives $36x \equiv 60 \mod 7 \implies x \equiv 4 \mod 7$ so we can easily deduce solutions ...