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
24 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
1answer
18 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
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
39 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
110 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
92 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
58 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
31 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
22 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
43 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
43 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
36 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?
0
votes
1answer
32 views

RSA cryptography

I saw on Wikipedia RSA algorithm and the private key has a condition imposed on it which says $$d \equiv e^{-1} \mod \phi(n)$$ where $n =(p-1)(q-1)$ but after a few steps $d$ condition becomes $$de \...
0
votes
1answer
20 views

System of congruences of 2 unknowns

Given constants $A, B, C, D$, and unknowns $x, m$, how would I go about solving a system such as this: $$A\equiv x B\mod m$$ $$C\equiv x D\mod m$$ I'm certain there is a very simple equivalent form of ...
2
votes
1answer
64 views

Fifth last digit of a huge number

How can I find the fifth last digit of $5^{5^{5^{5^5}}}$? I tried to evaluate $5^{5^{5^{5^5}}}\pmod {100000}$. But the exponent is so huge that I'm unable to evaluate it. Also, $(5,100000)=5$ , so $5$ ...
0
votes
0answers
23 views

Solving $n^{th}$ power residue of a congruence

I'm given $x^2$ ≡ -1 mod 365 I know that 365 = $5*73$ so then my congruence becomes, $x^2$ ≡ -1 mod 5 and $x^2$ ≡ -1 mod 73 Since $(-1)^2$ ≡ 1 mod 5 and $(-1)^{36}$ ≡ 1 mod 73 implies that there ...
0
votes
1answer
27 views

Find all $(a,b) \in \Bbb Z^2$ such that $b \equiv 2a \pmod 5$ and $28a+10b=26$

I'm stuck with this exercise: Find all $(a,b) \in \Bbb Z^2$ such that $b \equiv 2a \pmod 5$ and $28a+10b=26$ It's from my algebra class, we are looking into diophantic and congruence equations. ...
0
votes
2answers
51 views

Proof for any natural n that: $8|5^n+2*3^{n-1}+1$

I used this method for proving this statement but I came up with a problem. $ 5^n+2*3^{n-1}+1 \equiv 1 + 25^{n/2} + 2 * 81^{(n-1)/4} \equiv 4 \pmod{8}$ What is the problem with my solution?
1
vote
0answers
18 views

Is least prime factor of $n,$ $LPF(n)$ a solution to any congruence?

The greatest prime factor of $n$, $GPF(n)$ for $1\le j\le n$ can be represented as the number of solutions to the congruence $\displaystyle j!^n\equiv0\bmod n$ subtracted from $n+1.$ So I can ...
0
votes
1answer
35 views

Simultaneous congruence relations $x^a \equiv 1\pmod p$ and $x^b \equiv 1\pmod p$

Let $x$ be a natural number and $p$ a positive prime such that $\gcd(x, p)=1$. If $x^a \equiv 1\pmod p$ and $x^b \equiv 1\pmod p$, can we derive a relation between $a$ and $b$?
2
votes
1answer
31 views

How do I show that the product of even and odd number is always congruent to 2 modulo 4? [closed]

Here is what I have and I think I am really close. $(2k + 1) * 2l$ = $4kl + 2l$ EDIT My question is stupidly wrong, I probably meant to ask the product of odd number and even number not divisible ...
1
vote
2answers
23 views

Find $b \in \Bbb Z$ for which exists $a \equiv 4 \pmod 5$ such that $6a+21b=15$

I'm starting to study diophantic equations and congruence and I have found this problem that I don't know how to solve: Find $b \in \Bbb Z$ for which exists $a \equiv 4 \pmod 5$ such that $6a+21b=...
0
votes
0answers
15 views

Congruence for Bernoulli numbers

It appears that for every odd prime $p$, the following congruence holds for Bernoulli numbers: $$ 2pB_{p-1}-pB_{2p-2}\equiv p-1\mod p^2\mathbb{Z}_{(p)}. $$ The weaker statement that $2pB_{p-1}-pB_{2p-...
4
votes
2answers
56 views

How do you solve $x^2 - 4 \equiv 0 \mod 21$

There is an example in my textbook of how you solve: $$ x^2 -4\equiv 0 \mod 21 \Leftrightarrow x^2-4\equiv 0 \mod 3 \times 7$$ and then 2 congruences can be formed out of this equation if: $$x^2-4\...
3
votes
0answers
106 views

Find a solution to the congruence $x^3 \equiv$ $4 $ mod $ 5$

My question So there are three parts; (a) Find a solution to the congruence $x^3 \equiv$ $4$ mod $5$ by trying all possible $x$ values. (b) Find a solution to the congruence $x^3 \equiv$ $4$ mod $...
1
vote
4answers
179 views

Proving that an equation doesn't have integer solutions

I need to prove that there are no integer solutions for a bunch of equations like the following: $$15x^2 - 7y^2 = 9$$ I was able to solve some simpler ones by picking a dividend and looking into it's ...
4
votes
1answer
54 views

Prove that if $p \mid a-b$ then $p^{n+1} \mid a^{p^n}-b^{p^n}$

I need help with the following problem, I don't know how to continue. Let $p$ be a prime. Prove that if $p \mid a-b$ then: $$p^{n+1} \mid a^{p^n}-b^{p^n}$$ At first I thougt the following: $$p \mid ...
1
vote
1answer
26 views

Find the remainder for $\sum_{i=1}^{n} (-1)^i \cdot i!$ when dividing by 36 $\forall n \in \Bbb N$

I need to find the remainder $\forall n \in \Bbb N$ when dividing by 36 of: $$\sum_{i=1}^{n} (-1)^i \cdot i!$$ I should use congruence or the definitions of integer division as that's whave we've ...
1
vote
0answers
23 views

Solutions in $\mathbb Q_p$ leads to solution for congruences equations?

Let $p$ be a prime number such that $p\equiv1\pmod 3$. Let $n$ be an integer such that the equation $x^3=n$ has a solution in $\mathbb Q_p$. In fact with our assumptions, the others solution are in $\...
0
votes
0answers
28 views

Number of solutions of a difference-of-two-squares congruence with prime moduli

Problem: Show that if $p$ is an odd prime then $p-1$ number of ordered pairs $x, y$(unique modulo p) satisfy $x^2-y^2 \equiv a\mod p$ (for some given $a$ coprime to p). When $a \equiv 0 \mod p$ then ...
0
votes
0answers
43 views

Proving primality of $p$ without making any calculation involving $p$ directly

Wilson's Theorem states that a positive integer $p > 1$ is prime if and only if $(p-1)! \equiv -1 \pmod p$, showing a relationship between factorials and prime numbers. Finding it curious, today I ...
1
vote
0answers
26 views

$p \in \Bbb P, a \in \Bbb N$, then if $ord_p(a)=d$ we have $a^{d-1}+\dots+a+1 \equiv 0 \mod p$.

I want to prove the statement in the title, but I think we need $d \geq 2$ in the statement since otherwise there is a case not fulfilling the statement. My attempt: By assumption we have $ord_p(a)=:...