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

For all $x$ , $x^2 \equiv 0$ or $1$ or $4 \mod 7$

My textbook makes the following claim For any $x$ , $x^2 \equiv 0$ or $1$ or $4 \mod 7$ I can't see how this true though. $3^2 \equiv 4^2 \equiv 2 \mod 7$ so this obviously doesn't fall into ...
1
vote
0answers
15 views

$i \equiv k \mod p \implies i = k$ if $p$ is prime?

In a particular proof of Fermat's Little Theorem $\big(a^{p} \equiv a \mod p \big)$ in Engel, the following fact is used $i \equiv k \mod p \implies i = k \:$ where $p$ is a prime. I'm not really sure ...
0
votes
2answers
41 views

How many solutions of $\mod 63$ : $x^2=1 \pmod7 $ and $x^3=1\pmod 9$ [on hold]

How many solutions $\mod 63$ , we have for: $$x^2=1 \pmod 7$$ and $$x^3=1 \pmod 9$$ Need to find them also.
0
votes
2answers
34 views

Why does an even $x$ imply $y^2=-2 \pmod 8$

I am very new to modular arithmetic, and I encountered the following statement on page 7 of this paper: If $x$ is even then $y^2 \equiv-2\pmod{8}$ The equation in question is $y^2=x^3-2$ I do not ...
0
votes
2answers
23 views

Prove a linear congruence equation [closed]

Let $p$ be a prime number. Prove that $2(p-3)! ≡ -1\text{ (mod } p)$.
3
votes
2answers
30 views

For which $0\leq a<p^2$, where $p$ is an odd prime, we have that $(2p-1)!\equiv a\mod{p^2}$

Let $p$ be an odd prime. I need to find for which $0\leq a < p^2$, $(2p-1)!\equiv a\mod{p^2}$. If $a\equiv (2p-1)!\mod{p^2}$, then we have that $a = kp^2 + (2p-1)!$, and therefore $p\mid a$, ...
0
votes
2answers
29 views

Solving linear congruences with unknown modulus

I need to resolve the following system of linear congruences: $9 = 3a+c \pmod m$ $11 = 9a+c \pmod m$ $1 = 11a+c \pmod m$ How can I proceed? Is there anyway to input these equations in Wolfram ...
6
votes
3answers
52 views

Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$.

Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$. I'm having a difficult time proving this problem. I was able to verify that it works for prime $n$ up to ...
0
votes
1answer
19 views

Construct a function pertaining to the OEIS sequence A131229 (Numbers congruent to {1,7} mod 10)

OEIS sequence A131229 ("Numbers congruent to {1,7} mod 10") begins $\{1, 7, 11, 17, 21, 27, 31, 37, 41, 47, 51,...\}$. I want a function $f(x)$, specifically such that $f(\frac{1}{2}) =\frac{7}{2}$, ...
0
votes
1answer
37 views

What is a generalised solution for the Chinese Remainder Theorem?

I recently read that the system of congruences- $$x\equiv a_1\pmod {m_1}$$ $$x\equiv a_2\pmod {m_2}$$$$x\equiv a_3\pmod {m_3}$$...$$x\equiv a_k\pmod {m_k}$$ has a solution given by $$\sum_{i=1}^k\...
4
votes
2answers
82 views

Find $x$ in $1!+2!+\ldots+100!\equiv x \pmod{19}$

Here I come from one more (probably again failed) exam. We never did congruence with factorials; there were 3 of 6 problems we never worked on in class and they don't appear anywhere in scripts or ...
2
votes
1answer
43 views

When a congruence system can be solved?

How to prove that a congruence system with $n$ equations can be solved if and only if all the equations can be solved two by two? \begin{cases} x \equiv a_1 \phantom ((mod\phantom mm_1) \\ x \equiv ...
4
votes
1answer
28 views

Question on proof regarding solvability of congruences modulo powers of 2

The following theorem was left as an exercise in K. Ireland and M. Rosen's A Classical Introduction to Modern Number Theory. The theorem is as follows: Let $2^l$ be the highest power of 2 dividing ...
0
votes
3answers
74 views

Proving the Fermat's theorem

Fermat's theorem: if a is not divisible by p, then $a^{p-1} \equiv 1 \pmod p$ Since $\varphi(p)=p-1$, this is a special case of Euler's theorem. If $(a,m)=1$, then $a^{\varphi(m)}\equiv 1 \pmod m$. ...
2
votes
0answers
46 views

Proof about prime factors: every prime factor of $4n^2+1$ is congruent to $1 \pmod 4$. [duplicate]

Show that if $n$ is an integer, then every prime factor of $4n^2+1$ is congruent to $1 \pmod 4$. (Hint: if $p\mid 4n^2+1$), then what can you say about $(-1\mid p)$? Approach: I went over all the ...
1
vote
1answer
36 views

Does the equation $2^n \equiv r \bmod n$ have solution?

Given an integer $r$, is there a way to determine if there exists a positive integer $n$ such that $2^n \equiv r \bmod n$? What if the condition $0 \leq r < n$ is required? I came up with this ...
0
votes
2answers
56 views

Bounding solutions of a diophantine equation

Let $k$ and $s$ be natural numbers such that $s^2-s+1 \equiv 0 \pmod{k}$. Consider the equation $$ -si+(s-1)j \equiv 0 \pmod{k} $$ In all examples of pairs $(s,k)$ that I've tested, I got $(i+j)^2>...
1
vote
1answer
35 views

Primitive 18-th root of unity problem involving congruences.

I have some doubts about this following problem, if you can please try to answer the congruence step: Let $ \omega$ be a primitive 18-th root of unity. Find $ n \in \mathbb Z$ such that: $ \omega^n =...
1
vote
1answer
34 views

Number Theory Lemma About Linear Congruence (Explanation Needed)

I was reading Elementary Number Theory Second Edition by Dudley Underwood, and I came across what appeared to me to be a contradiction in chapter/section 5. The book says: If one integer satisfies $...
0
votes
3answers
35 views

Question about linear congruences

Consider the congruence $$2x+7y \equiv 5\pmod{12}$$ Here $(2,7,12)=1$. Since $(2,12)=2$, we must have $$7y \equiv 5\pmod{2}$$ Which clearly gives $y \equiv 1\pmod{2}$, or $y \equiv 1,3,5,7,9,11\...
0
votes
1answer
22 views

Confusion in reduced residue systems

1 and 5 constitue a reduced residue system (mod 6). The book says a set of integers $a_1,...,a_h$ is a reduced residue system if it's incongruent (mod m) and relatively prime to m, such that if a is ...
-1
votes
2answers
33 views

Show that if $a\equiv b \pmod m$, then $\gcd(a,m)=\gcd(b,m)$ [duplicate]

I still don't have a clear approach, but this is what I see. $m \mid b$ and $m \mid a$ or $m\nmid b$ and $m\nmid a$. I may think that the way is showing $\gcd(a,m)\leq\gcd(b,m)$ and $\gcd(a,m)\geq\...
1
vote
3answers
62 views

Find $\overline{0},\overline{1},\overline{10}$ and $\overline{16}$ in $\mathbb{Z}_5$

Find $\overline{0},\overline1,\overline{10}$ and $\overline{16}$ in $\mathbb{Z}_5$ I know that the bar above the number means the congruence modulo. $\overline{a}:=\{x\in \mathbb{Z}:x\equiv a \pmod ...
3
votes
0answers
44 views

Is there an identity related to $\binom{n-j-1}{k}+\binom{k+j}{k}\pmod{n}$?

I noticed that when $n$ is an odd prime, the following congruence $$\binom{n-j-1}{k}+\binom{k+j}{k} \equiv 0 \pmod{n}$$ holds for $0 \le j \le \frac{(n-k)}2$ and odd values of $k$ such that $0 < k ...
2
votes
4answers
113 views

Is this possible to solve through algebra?

$$150 \equiv 17 \mod x, \qquad 100 \equiv 5 \mod x $$ Solve the simultaneous equation? Is this even a simultaneous equation? How do I find the value of $x$ too? I was doing a question and came up ...
0
votes
2answers
35 views

Module Exponential problem

Here is the problem: $ 445^{445} + 225^{225} $ mod 7 So, I know how to calculate this $445^{445}$ and this $225^{225}$ separately. But i don't know how to add them and then mod 7. In other words ...
2
votes
4answers
93 views

how to solve $x^{113}\equiv 2 \pmod{143}$

I need to solve $x^{113} \equiv 2 \pmod{143}$ $$143 = 13 \times 11$$ I know that it equals to $x^{113}\equiv 2 \pmod{13}$ and $x^{113}\equiv 2 \pmod{11}$ By Fermat I got 1) $x^{5} \equiv 2 \pmod{...
3
votes
1answer
115 views

Can it be proven using congruence?

We now that $a^3 +b^3=c^3$ has no solution if $a,b,c\in\mathbb{N}$(thus non of $a$, $b$ or $c$ can be zero). Well I want to know whether this can be proven using congruency(Like how we can prove that ...
0
votes
1answer
39 views

What does congruency mean in $D_4$?

What does congruency mean in $D_4$? How can I check for example that For $K = \{k_0, k_2\}$, $$p_x \equiv p_y \pmod K$$ I.e. how to evaluate $(p_x - p_y) \bmod K$, specifically what is $(p_x - p_y)...
3
votes
1answer
63 views

Is $S_i(1,2,\dots,p-2) \equiv 1 \pmod{p}$ for all values of $i$ whenever $p$ is prime?

Let $S_i(x_1,x_2,\dots,x_n)$ denote the $i$th elementary symmetric polynomial in $n$ variables. Is $S_i(1,2,\dots,p-2) \equiv 1 \pmod{p}$ for all values of $i$ from $0$ to $(p-2)$ whenever $p$ is ...
0
votes
1answer
33 views

System of linear congruence when not relatively prime

I am new to Abstract Algebra and understand how to solve when the mods are relatively prime, but I am struggling when they aren't relatively prime. I have a system of of linear congruences that I ...
1
vote
1answer
23 views

How can i prove that if $x_0$ is a solution then $[x_0]$ is unique?

$4x\equiv10\pmod6$ I'm not sure what they asking when they say that the equivalence relation of a solution is unique. Also I was able to find the solution -5 with euclids algorithm, is there a more ...
2
votes
1answer
88 views

Solve congruence

Solve:$$ \underbrace{2 ^ {2 ^ { {...} ^ 2 }}}_\text{2016} \pmod {2016}$$ So $ 2016 = 2^5 \cdot 3^2 \cdot 7$ And $$ \underbrace{2 ^ {2 ^ { {...} ^ 2 }}}_\text{2016} \pmod{2^5} \rightarrow \underbrace{...
0
votes
1answer
39 views

The difference between congruence and equivalence class?

I've got an excercise solved by my teacher, it says I've got to prove a relation $R$ of elements in $\mathbb{R}^2$ is a congruence. In the solved exercise he just proved Reflexivity, transitivity and ...
0
votes
1answer
45 views

Help with finding the remainder of $2^{2^n}$ when divided by 13

I have this problem from an algebra course: Find the remainder of $2^{2^n}$ when divided by 13, $\forall n \in \Bbb N$ It's in a section of Fermat's little theorem and Chinese Remainder Theorem ...
2
votes
1answer
15 views

Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$. Find the remainder of $a$ when divided by 70.

I'm stuck with this problem from my algebra class. We've recently been introduced to Fermat's little theorem and the Chinese Remainder Theorem. Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$...
1
vote
5answers
53 views

How do I solve this congruence?

I have some difficulties solving the following congruential equation. $3n^2 + 2 ≡ 0\pmod 5,\ \forall\ n \in Z$ If I subtract both members by $-2$, I end up getting $3n^2 = -2\pmod 5$ and I can't ...
0
votes
2answers
44 views

Quadratic residue $p \equiv 1 \pmod 4 $

Suppose $p$ is a prime congruent to $3$ modulo 4. Additionally, suppose $a$ is a quadratic residue modulo $p$. Prove that $x=a^{\frac{p+1}4}$ is a solution to the congruence $x^2\equiv a \pmod p$ ...
4
votes
3answers
77 views

Prove the congruence $ \sum_{r=1}^{p-1}{(r|p) * r } \equiv 0 \pmod p.$

Prove that if $p$ is prime and $p\equiv 1 \pmod4$, then $$ \sum_{r=1}^{p-1}{(r|p) * r } \equiv 0 \pmod p.$$ ( $(r|p)$ is a Legendre Symbol ) I know that $\sum_{1 \le r \le p}{(\frac{r}{p})} = 0$, but ...
3
votes
1answer
37 views

Prove that $x^{n}\pmod {(x^{4}+1)}=x^{n \pmod 4}$

Assume $GF(2^k)[x]$ (where $k$ is a fixed natural number) is a ring of polynomials with coefficients in the field $GF(2^k)$. Prove that for every polynomial $x^n$ (where $n \in \mathbb{N}$) from $GF(2^...
0
votes
1answer
33 views

$5$ is quadratic residue mod $p$ if and only if $ p\equiv \pm 1, \pm 9 \pmod {20}$

5 is quadric residue mod p if and only if $ p\equiv +/- 1, +/-9 \pmod {20}$ $$(5/p)=(p/5)$$ $p\equiv 1 \pmod 4$ ⟹ $1,5,9,13,17 \pmod {20}$ $p\equiv 1 \pmod 5$ ⟹ $1,6,11,16 \pmod {20}$ then $p\...
-1
votes
2answers
37 views

-3 is quadratic residue if and only if $p \equiv 1,7 \pmod {12}$ [closed]

I have to prove that -3 is quadratic residue if and only if $$p \equiv 1,7 \pmod {12}$$ I know one method (with symbol Legendre'a) but I don't get. If someone can explain me I will be happy or give ...
0
votes
1answer
40 views

Prove that $2^d$ is not congruent to $1 \mod p^2$

We have $p>2$ - prime number and we know that $2^n\equiv 1\mod p$ and $2^n$ is not congruent to $1 \mod p^2$ ($n$-natural number). Prove that $2^d$ is not congruent to $1 \mod p^2$ where order $2 = ...
3
votes
2answers
27 views

Solve the congruence system: $p \equiv 11\pmod{24}$ and $ p\equiv 3 \pmod 4$

I want to find the solutions of the congruences system: $p \equiv 11\pmod{24}$ and $ p\equiv 3 \pmod 4$. I probably have some mistake in my solution, can you tell me where I'm wrong? $ 4 $ and $...
0
votes
0answers
27 views

Prove: If $ p|2^q -1$, p,q primes numbers then p is congruent to 1 modulo q

p|2^q -1, so 2^q - 1 = pk and 2^q = pk - 1 from Fermat we've got 2^q is congruent to 2 (mod q) pk-1 is congruent to 2 (mod q) pk is congruent to 1 (mod q), then k must be 1 Is this evidence ...
0
votes
1answer
30 views

Computing difference in modular arithmetic. [closed]

Is there a meaningful kind of difference "$|a-b|$" in modular arithmetic? For example, in mod $12$, we would like to have $|0-11|= 1$ and $|0-1| = 1$.
2
votes
2answers
64 views

What is the Least Prime Factor of $3^{3241} + 8^{2433}$

I'm not sure how to do this question Attempt $$3^{3241} + 8^{2433}$$ I start by taking this number mod 3 $$3^{3241} + 8^{2433} \equiv 8^{2433} \mod 3$$ No we can see that $8^2 \equiv 1 \mod 3$. So $$...
0
votes
1answer
20 views

Congruences and Legendre

I am trying to solve a Legendre symbol problem and have got it down to the following: When $p \equiv 1\mod4$ and a prime such that $p \neq 2,7$, $\left(\frac{7}{p}\right) = \left(\frac{p}{7}\right)...
0
votes
1answer
28 views

Is it true that if $ -p \equiv -1 \pmod q $, then $p \equiv 1 \pmod q $? [closed]

Is it true that if $ -p \equiv -1 \pmod q $, then $p \equiv 1 \pmod q $? p and q are prime numbers.
1
vote
5answers
151 views

Solve $ord_x(2) = 20$

Given that the (multiplicative) order of $2$ mod $x$ is $20$, how can I work out what $x$ is?