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

-2
votes
2answers
45 views

How to find $x$ value such that $x^5\equiv 99 \pmod{21}$ using congruences

I know congruences somewhat, however this problem is troubling me a lot. Please help me. If $17^5\equiv 5 \pmod {21}$, then at what value of x, $x^5\equiv 99 \pmod{21}$? High regards, ZION
0
votes
3answers
48 views

Chinese remainder theorem for three equations?

Is there a straightforward approach for solving the Chinese Remainder Theorem with three congruences? $$x \equiv a \bmod A$$ $$x \equiv b \bmod B$$ $$x \equiv c \bmod C$$ Assuming all values are ...
0
votes
0answers
52 views

Curious GCD Divisibility Relation

In some of my recent work, I have accidentally discovered in an extremely convoluted manner the following result: Suppose $a,b$ are positive integers less than some other positive integer $c$, and ...
3
votes
2answers
37 views

Congruence rules when solving equation

I am trying to solve the following congruence problem. 980x ≡ 1500 mod 1600 The steps I came up with were as follows: 980x ≡ 1500 mod 1600 49x ≡ 75 mod 80 (Divide by 20, gcd(20, 1600) = 20 so 80 = ...
1
vote
0answers
16 views

Number of solutions to quadratic congruence

For every positive integer $b$, show that there exists a positive integer $n$ such that the polynomial ${x^2} - 1 \in (\mathbb{Z}/n\mathbb{Z})[x]$ has at least $b$ roots. My efforts Let $n = ...
0
votes
1answer
25 views

Proving B Congruent C given AB congruent AC

This is a very trivial question, i seem to have arrived at a proof for an excercise but the proof just doesn't feel.. right. It is too small and simple. The fact to be proved is that if $AB\equiv AC$ ...
1
vote
2answers
39 views

If $p$ is a prime number and $p\equiv 1(mod 4)$, (show that) there exist integers $a$ and $b$ such that $a^{2}+b^{2}=p$.

I'm reading a book on number theory (Theory of Numbers, Niven), and yesterday I've stumbled upon a proof of the above lemma (Lemma 2.13; page 54-55). I've managed to wrap my mind around the proof from ...
3
votes
4answers
50 views

How do I show that we can't write $N=114^n-1$ as sum of $3$ squares for all natural number $n>2$?

I run some computations in wolfram alpha, I see that we can't write :$$N=114^n-1$$ as sum of $3$ squares, then Hop someone who can show me how I do prove that we can't write $N=114^n-1$ as sum of $3$ ...
1
vote
1answer
52 views

Using Fermat's little theorem to find $9^{45} \mod 23$

I used Fermat's Little Theorem to find: $$9^{45} \mod 23$$ What I have done so far: $$9^{45} = (9^2)^{22}9$$ $$9^{22} \equiv 1 \pmod{23}$$ According to Fermat's Little Theorem. So, now I have: ...
1
vote
2answers
27 views

Is this a correct solution to the linear congruence?

I want to solve this linear congruence: $$2x \equiv 5 \pmod{9}$$ Backward substitution: $$9 = 4 \cdot 2 + 1$$ $$4(-2) + 9 = 1$$ Therefore, the inverse is: $-2$ Now multiply the linear congruence ...
0
votes
2answers
21 views

Modular arithmetic exponentiation

Does modulus apply to exponents as well. eg Let $ xy \equiv 1 (mod\;m).$ then does $a^{xy} \equiv a^{1} (mod\;m)$ ?
0
votes
0answers
22 views

Find multiplicative inverse and order of elements in group of units modulo $501$ and $4061$

Find the inverse of the following elements : Find $[91]^{-1}$, if possible (in $\Bbb Z^*_{501}$). Find $[3379]^{-1}$, if possible (in $\Bbb Z^*_{4061}$). Now, we have $\phi(501)=332$ and ...
0
votes
0answers
12 views

Method for solving $x ^k \equiv b\pmod m$ with $\gcd(b, m) > 1$

A method for solving $x^k \equiv b\pmod m$ with $\gcd(b, m) = 1$ involves finding positive integers $u$ and $v$ that satisfy $ku - \phi( m ) v = 1$ and computing $b^u \pmod m$. It is easy to show that ...
-1
votes
0answers
19 views

Find a particular order of elements in group of units modulo $100$. [duplicate]

Let $\mathbb Z^*_{100}$ be a group of units modulo $100$, i.e., $\mathbb Z^*_{100}=\{1,3,7,9,13,17,19,\dots,97,99\}$. Find such $a\in \mathbb Z^*_{100}$ such that the order of $a$ is $20$ in $\mathbb ...
1
vote
1answer
24 views

A congruence for the prime counting function in Wolfram.What does it actually say?

I saw today in functions.wolfram.com a congruence for the prime counting function which says $\binom {2prime(k)-1} {prime(k)-1} \pmod{prime(k)^3}=1$ (the third congruence at the bottom). What does ...
2
votes
1answer
59 views

Find total number of elements of order 20 in the multiplicative group $\mathbb Z^*_{100}$

How can I find all the elements of order $20$ in the multiplicative group $\mathbb Z^*_{100}$. $[7]\in \mathbb Z^*_{100}$. $7^4\equiv 1\pmod{100}$. So order of $[7]=4$. But how can I find all ...
4
votes
1answer
204 views

How do I prove that there is no other :$k=9,12,18$ for which this fails :$\sigma^k(114) \equiv 0\mod 6 $?

let $\sigma(n)$ be the sum of divisors for a positive integer for example : $$\sigma(6)=1+2+3+6=12$$ . I have performed some calculations in wolfram alpha about the sum divisors of this number: ...
3
votes
3answers
51 views

Is this formula true for $n\geq 1$:$4^n+2 \equiv 0 \mod 6 $?

Is this formula true for $n\geq 1$:$$4^n+2 \equiv 0 \mod 6 $$. Note :I have tried for some values of $n\geq 1$ i think it's true such that :I used the sum digits of this number:$N=114$,$$1+1+4\equiv ...
1
vote
0answers
36 views

Modular fractions: $5 \big| 3- \frac 12$

I've read a lot here about how modular fractions are valid as long as the denominator is invertible, but they always cause me trouble understing this part: From the definition of congruence: $$ a ...
2
votes
2answers
70 views

How can I simplify $123^{11} \mod 323$?

I am busy studying the RSA cryptosystem and would like to know how to simplify things like this: $123^{11} \mod 323$
2
votes
4answers
126 views

An easy way to calculate $12^{101} \bmod 551$?

We learn about encryption methods, and in one of the exercises we need to calculate: $12^{101} \bmod 551$. There an easy way to calculate it? We know that: $M^5=12 \mod 551$ And $M^{505}=M$ ($M\in ...
1
vote
3answers
34 views

How to determine congruence manually

How is it possible to determine if the the following congruence is true manually? $$ 2015^{53} \equiv 8 \pmod{11} $$
0
votes
4answers
41 views

How to manually determine big number congruences

How is it possible to determine if the the following congruence is true manually, with resort to a basic calculator? The real problem here is how to do the math with a such big number? $$ 2015^{50} ...
1
vote
4answers
34 views

system of modular equations.

$x\equiv 2\pmod3$ $x\equiv 3\pmod 5$ $x\equiv 7 \pmod{11}$ How can I solve this system for $x$? I've tried all kinds of things using divisibility but no success. Any hints of solutions are greatly ...
6
votes
7answers
204 views

Calculating remainder of $666^{666}$ when divided by $1000$.

I want to calculate the remainder of $666^{666}$ when divided by $1000$. But for the usual methods I use the divisor is very big. Furthermore $1000$ is not a prime, $666$ is a zero divisor in ...
0
votes
3answers
32 views

Double modular exponent with Euler-Fermat

$$7^{3^{18}} \pmod{9}$$ Using this formula : $a^{\phi(m)} \equiv 1 \pmod m$ I got $7^6 \equiv 1 \pmod{9}$ and I can write $3^{18}$ as $3^6 \cdot 3^3$ And what are next steps? I got stuck here.
2
votes
1answer
22 views

Find all values of $p$ such that $ax^2+bx+c \equiv 0 (\bmod p)$ have solution

Is there a general way to find all values of $p$ such that the congruence $ax^2+bx+c \equiv 0 (\bmod p)$ have solution, we can assume that $ax^2+bx+c =0 $ have solution.
-1
votes
2answers
50 views

Is this problem correct? [duplicate]

I have found another problem in my book. I have to prove that $$2^{70}+3^{70}$$ is divisible by 13. But I have proven that $2^{70}\equiv 12 (mod 13)$ and $3^{70}\equiv 3 (mod 13)$ so it is ...
2
votes
2answers
54 views

Prove that $2^{15}-1$ is divided by $11\cdot31\cdot61$?

I have to prove that $2^{15}-1$ is divided by $11\cdot31\cdot61$. I have proven using congruencies that $2^{15}-1$ is divided by $31$. However we have $$2^5\equiv 10 \mod{11}$$ $$2^{15}\equiv ...
1
vote
2answers
63 views

How can I find the remainder?

How can I find the remainder when $$(12371^{56}+34)^{28}$$ is divided by $111$. I have tried congruences modulo $111$ but without any success.
4
votes
0answers
26 views

Proving that there exist products of $a_k \equiv 1 \pmod {a_i}$ [closed]

Let $n>2$ be an integer. Prove that there exist numbers $a_1, a_2, \ldots ,a_n$ such that $$a_1a_2\cdots \widehat{a_i}\cdots a_n \equiv 1 \pmod{a_i}$$ for $i=1,2,3,\ldots,n$. Here ...
1
vote
1answer
35 views

$r! \equiv (−1)^k \pmod p$

Suppose that p ≡ 3 (mod 4) and $r = \frac {p-1}2$ Show that $r! \equiv (−1)^k \pmod p$ where k is the number of non-quadratic residues modulo p which are smaller than $\frac p2$ I know from ...
0
votes
1answer
30 views

Show that $(r!)^2 ≡ (−1)^{r−1} \pmod p$ [duplicate]

I need to prove that if p is an odd prime and $r = (p-1)/2$ then $(r!)^2 ≡ (−1)^{r−1} \pmod p$ I think it has something to do with gauss's lemma ...
1
vote
2answers
63 views

solve $x^2 \equiv 24 \pmod {60}$

I need to solve $x^2 \equiv 24 \pmod {60}$ My first question which confuses me a lot - isn't a (24 here) has to be coprime to n (60)??? most of the theorems requests that. what i tried - $ 60 ...
0
votes
1answer
20 views

Show how one can decrypt RSA message with e = 3 and $m<N^{1/3}$ without knowing the private key

Show how one can decrypt RSA message with e = 3 and $m<N^{1/3}$ without knowing the private key. I really don't know how to solve this one. we just learned about quadratic residues so i guess it ...
3
votes
2answers
56 views

$x^2 + 3x + 7 \equiv 0 \pmod {37}$

I'm trying to solve the following $x^2 + 3x + 7 \equiv 0 \pmod {37}$ What I've tried - I've tried making the left side as a square and then I know how to solve but couldn't make it as a square ...
0
votes
2answers
52 views

solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$

I need to solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$ I saw the same problem here - Solving the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$ but didn't understand how he got to the conclusion ...
5
votes
4answers
89 views

How do I calculate $2^{47} \pmod{\! 65}$?

I'm trying to calculate $2^{47}\pmod{\! 65}$, but I don't know how... I know that: $65=5\cdot 13$ and that: $2^{47}\equiv 3 \pmod{\! 5}$ and $2^{47}\equiv 7\pmod{\! 13}$... (I used Euler) But ...
3
votes
2answers
43 views

Find all the solutions of $y^2 \equiv 5x^3 \pmod 7$

I need to find all the solutions of $y^2 \equiv 5x^3 \pmod 7$. I managed to solve by trying one-by-one, but I guess there is some other way to solve this.
1
vote
1answer
34 views

prove that $(1+pt)^{p^{r-1}} \equiv 1 \pmod {p^r}$

I need to prove that $(1+pt)^{p^{r-1}} \equiv 1 \pmod {p^r}$ the original question is this: Prove that , any primitive root $r$ of $p^n$ is also a primitive root of $p$ and I'm following the ...
5
votes
2answers
93 views

Solve $x^8 \equiv 3 \pmod {13}$

I need to find all solutions to $x^8 \equiv 3 \pmod {13}$. What I've tried: I know $2$ is a primitive root modulo $13$. So it is equivalent to solve $2^{8t} \equiv 2^4 \pmod {13}$ Then I get $t = ...
1
vote
1answer
24 views

Using modular arithmetic to evaluate a modulo operation

I needed to evaluate $3^{100} \pmod 7$ by hand. So, I made a list of increasing powers of $3 \pmod 7$ like so: $3^1 \equiv 3 \pmod 7$ $3^2 \equiv 2 \pmod 7$ $3^3 \equiv 6 \pmod 7$ (1) ... $3^6 ...
2
votes
2answers
44 views

Show that the number of solutions of $x^2 \equiv 1 \pmod n$ is 2

let $3 \le n \in N$ for which there exists a primitive root modulo n. Show that the number of solutions of $x^2 \equiv 1 \pmod n$ is 2 what it tried - i tried showing x and 1 as the primitive root ...
2
votes
1answer
24 views

Solving for solutions to a congruence

I am interested in solutions to this congruence: $$2^kx \equiv x \bmod m$$ Where $m$ and $x$ are known positive integers. They may not necessarily be prime or coprime. I am looking for solutions for ...
8
votes
2answers
187 views

$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?

From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
4
votes
1answer
43 views

Solve $7^x \equiv 6 \pmod{17}$ given 3 is a primitive root $\bmod 17$

It's easy to show that 3 is a primitive root $\bmod 17$, but how do I use it prove the congruence? Is there a general way to solve any congruence of the form $a^x \equiv b \pmod{c}$ if you know a ...
1
vote
2answers
46 views

Solving a quadratic relation mod $13$

Solve for $x$ in $x^2 +2x +1\equiv 2 \pmod{13}$ I started with $2^{12}\equiv 1 \pmod{13}$ by Fermat's Little Theorem. I found no square root of $2$ from $(x+1)^2\equiv 2 \pmod{13}$ using a ...
1
vote
1answer
33 views

What's the remainder when $100!+5400$ is divided by $124$?

I'm pretty much stuck on this one because of the factorial. In this case, how can I solve it?
0
votes
2answers
24 views

Equivalence of congruences - why are these congruences equivalent?

I'm reading a solution of the following congruence: $x^{59} \equiv 604 \mod 2013$. It says that it is equivalent to the following system of congruences: $$\begin{cases} x^{59} \equiv 604 \mod 3 \\ ...
0
votes
2answers
60 views

Abstract Algebra - Congruence Class Roots

How do we find the roots of ${x^3 + x + 1}$ in $ {Z_2[x]} $ The elements of the congruence class are: $$0, 1, x, x + 1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1$$ as they have to be of the form $ax^2 + bx ...