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

Solving problem of abstract algebra [on hold]

The question is that if $n$ is not a multiple of 23 then the remainder when $n^{11}$ is divided by 23 is 1 or -1(mod 23). Is it true or false? Please answer me.
3
votes
0answers
68 views

Solving an equation $x^{22}\equiv2 \bmod 23$ [on hold]

I have an abstract algebra problem which I am unable to solve. The problem is, if $x^{22}\equiv2 \bmod 23$, then $x$ has how many solutions? Please explain me.
3
votes
1answer
27 views

Prove $v,w\in Z_{p}\times Z_{p}$ is linearly independent when $p=2$ and dependent when $p=3$

I need to prove that $\{v=(6,9),w=(7,8)\}\in Z_{p}\times Z_{p}$ is linearly independent when $p=2$ and linearly dependent when $p=3$. The problem is my freshman algebra course did not cover rings and ...
0
votes
2answers
21 views

Simulataneous equations

Suppose you have the following system of linear congruence 2x+5y is congruent to 1 (mod6) x+y is congruent to 5 (mod6) where x,y belong to the set of Integers How would you obtain a general ...
2
votes
2answers
58 views

Can this congruence be simplified?

$$p(p+1) \equiv -q(q+1) \bmod pq$$ Can this be reduced to an easier format?
2
votes
1answer
14 views

solving $\left( m'\right) ^{d}\equiv m\cdot m^{r\left( p-1\right) \left( q-1\right) }\left( mod\ p\right) $

maybe someone can help: I am trying to follow a lecture and there is: given : $\left( m'\right) ^{d}\equiv m\cdot m^{r\left( p-1\right) \left( q-1\right) }\left( mod\ p\right) $ and : $ m^{p-1} ...
0
votes
3answers
49 views

Solve the congruence $31x\equiv 5 \pmod{23}$

I've used the Euclidean Algorithm to solve congruences of the form $$ax \equiv b \pmod n$$ where $n >a$, for example: $16x \equiv 5 \pmod{29}$. When $n <a$, for example, $$31x \equiv 5 ...
2
votes
1answer
45 views

Sum of digits modulo a polynomial

I made the following problems a while ago but I can't solve them (though I don't think it's too hard) 1.Let $s(n)$ be the digits sum of $n$. Let also $f(n)$, $g(n)$ $\in Z[X]$ . Assume that: ...
2
votes
2answers
26 views

Calculate cycle length

let $a, n, m \in \mathbb{Z}$ and $i\in\mathbb{N}$ and $$(a+in) \mod m$$ Is there a closed way to tell for what $i$ the congruence begins to cycle? Thanks
2
votes
1answer
37 views

Ordered triples of n-powerful integers

Let’s say that an ordered triple of positive integers (a, b, c) is n-powerful if: $a \le b \le c$, $gcd(a, b, c) = 1$ and $a^n + b^n + c^n$ is divisible by $a + b + c$. For ...
0
votes
0answers
26 views

Congruence on inverse semigroup

Could you please help me to understand the reason why we are interested in trace of a congruence and the kernel's congruence when we're talking about the congruences on inverse semigroup. also I have ...
0
votes
1answer
59 views

Something related to carmichael numbers.

$a^{n - 1} = 1 \bmod n$ for any prime $n$ and any $a$ prime to $n$. Yet there exists composite $m$ such that $a^{m-1} = 1 \bmod m $ for all $a$ relatively prime to $m$; $m$ being a Carmichael number, ...
20
votes
13answers
2k views

Why do we use “congruent to” instead of equal to?

I'm more familiar with the notation $a \equiv b \pmod c$, but I think this is equivalent to $a \bmod c = b \bmod c $, which makes it clear that we should put a $=$ instead of $\equiv$. What's the ...
1
vote
0answers
46 views

Solving quadratic congruences

System of equation is : $$ x^2 \equiv 2 \mod 3 $$ $$ x^2 \equiv 4 \mod 5 $$ So, if first equation doesn't have solution what should I do with it?
2
votes
2answers
70 views

Remainder of division of ${6}^{7^n}$ to $43$

What is the Remainder of the division of ${6}^{7^n}$ to $43$? I've tried with Fermat's little theorem, but it haven't work. Update : lab bhattacharjee gave a nice proof. But I want to know if ...
0
votes
1answer
28 views

How do I solve this system of residue class equations?

$$\overline{3}x+\overline{2}y=\overline1$$ $$\overline{5}x+y=\overline4$$ both in $\Bbb{Z}_7$ So I multiple the second by 2 to get $\overline{10}x+\overline2y=\overline8$. Then I subtract the first ...
0
votes
2answers
36 views

If $p_i$ is prime then $p_i \Bbb Z \cap p_j \Bbb Z= \emptyset \ \forall i,j \in \Bbb N, i\neq j$.

If $p_i$ is prime then $p_i \Bbb Z \cap p_j \Bbb Z= \emptyset \ \forall i,j \in \Bbb N, i\neq j$. Where $a \Bbb Z=\{x\in \Bbb Z: x=0 \mod a\}$. I ran into some problem where having this lemma proved ...
1
vote
3answers
67 views

Question about congruence modulo n

Is there any sort of algorithm to calculate the remainder when $10^{515}$ is divided by $7$? Could the same algorithm be applied to finding the remainder of $8^{391}$ divided by $5$? Is it even ...
0
votes
1answer
22 views

Does coprimality also extend to inverses?

For example, consider the congruence, for positive $x,y$ $$5^{y-10} = x5^{y-10} \bmod 64$$ Is it safe to divide both sides by $5^{y-10}$? Clearly if $y-10$ is non-negative, it will be coprime to 64 ...
3
votes
3answers
46 views

Solving simple mod equations

Solve $3x^2 + 2x + 1 \equiv 0 \mod 11$ Additionally, I have an example problem, but a step in the middle has confused me: $3x^2 + 5x - 7 \equiv 0 \mod 17$. Rearrange to get $3x^2 + 5x \equiv 7 \mod ...
1
vote
1answer
20 views

Solving $x^2\equiv a\pmod{p}$ where $p\equiv5\pmod{8}$ and $a$ is a quadratic residue

The exercise asks me to show that one of the values $x = a^{(p+3)/8}$ and $x = 2a \cdot (4a)^{(p-5)/8}$ is a solution to $x^2\equiv a\pmod{p}$, where $p\equiv5\pmod{8}$ is a prime and $a$ is a ...
4
votes
1answer
56 views

$\lfloor x^k \rfloor \equiv m \pmod{n}$ with $x$ irrational

Let $x>1$ be an irrational number, and $n$ a positive integer. Is it true that, for each integer $m$, there exists an integer $k$ such that $$ \lfloor x^k \rfloor \equiv m \pmod{n}? $$
-2
votes
2answers
50 views

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

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
52 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
61 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
49 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
40 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
52 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
57 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 ...
2
votes
1answer
27 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
60 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
214 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
76 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
129 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
35 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
42 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
6answers
226 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
33 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
58 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
64 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.