For question about the properties or calculation of congruences and congruences equation, and related theorems of congruences like chinese remainder theorem, Fermat's little theorem and Euler's totient theorem.

learn more… | top users | synonyms

2
votes
5answers
68 views

How to prove that $8^{18} - 1$ is divisible by $7$ [duplicate]

How to prove that: $$ 8^{18}-1\equiv0\pmod7 $$ In the simplest way?
1
vote
1answer
29 views

Verify proof that ${p \choose r} ≡ 0 \pmod p$

Let $p$ be a prime number. For any $1 ≤ r ≤ p − 1$, prove that $${p \choose r} ≡ 0 \pmod p$$ I'm thinking that it suffices to show $p$ divides ${p \choose r}$. So then: $$\begin{align} p\ |\ {p ...
1
vote
1answer
35 views

About primitive roots and square free numbers.

Are primitive roots usually square-free or prime? If ($m^2$ n) is a primitive root then n is a non-quadratic residue. Given there are $\phi{(p-1})$ primitive roots mod p then for some large prime p ; ...
0
votes
1answer
14 views

Solving a congruence — where to start?

For which positive integers $n$ is it true that $$1^2 + 2^2 + \cdots + (n − 1)^2 \equiv 0 \,(\text{mod } n)$$ I have no idea where to start. I'm just looking for a nudge in the right direction. Any ...
1
vote
0answers
26 views

If $\lambda\subseteq\mathscr{L}, \rho\subseteq\mathscr{R}$, then $\lambda\circ\rho=\rho\circ\lambda$.

This is (the first part of) Exercise 2.4 of Howie's Fundamentals of Semigroup Theory. The Details. Quoting Howie (on page 22 of my copy): Definition: A relation $R\subseteq S\times S$ on a set ...
-1
votes
1answer
24 views

Congruences in Algebra [on hold]

I have a question regarding a particular statement of a given Ring Theory problem. It is "$x$ is unique mod $n=n_1n_2...n_k$". Can anyone please tell me the meaning of this statement?
-1
votes
1answer
18 views

Solution of congruence relation

The congruence relation $x^{n}≡2\pmod{13}$ has a solution for (a) n=5 (b) n=6 (c) n=7 (d) n=8 ? Are there any method to find the value of n?Putting the values of n & finding the solution is very ...
0
votes
1answer
13 views

Cant Solve this Indices Question

I been surfing all related stuff concerning solving indices but all I got are congruence solved using indices and i dont even know if that the one im looking for, im trying to solve this question ...
2
votes
1answer
79 views

Prove that $r(2^{55555})$ divisible by $5^5$

In this question there is a comment by @amclade, that $$r\left(2^{55555}\right) \equiv 0 \pmod{5^5},$$ where $r : \mathbb{N} \rightarrow \mathbb{N}$ function gives the reverse of a number. I've ...
0
votes
2answers
26 views

Find the least positive residue of $5^{16} \bmod 17$

I need some help on finding the least positive residues. Not sure what the correct approach is to take on these types of problems and the book I'm reading isn't helping me. ** UPDATE ** If 17 was ...
1
vote
1answer
26 views

Find the remainder of $(p-2)!$ module $p$, where $p$ is a prime $\geq 3$

My attempt: From Wilson's Theorem: For a prime $p$, $$(p-1)! \equiv (-1) \pmod p$$ Multiplying both sides by $(p-2)$, $$(p-2)! \equiv -(p-2) \pmod p$$ i.e. $$(p-2)! \equiv 2 \pmod p$$ So the ...
0
votes
1answer
42 views

For any integer $a,b$ let $N_{a,b}$ denote the number of positive integer $x<1000$ satisfying $x= a( mod\;27)$ and $x=b(mod\;37)$. Then

For any integer $a,b$ let $N_{a,b}$ denote the number of positive integer $x<1000$ satisfying $x= a( mod\;27)$ and $x=b(mod\;37)$. Then which of them is correct (1) there exist $a,b$ such that ...
0
votes
0answers
23 views

Euler's Theorem when $m$ is square-free

Suppose that $m$ is square-free, and that $k$ and $\bar{k}$ are positive integers such that $k\bar{k} \equiv 1\pmod{\phi(m)}$. Show that $a^{k\bar{k}} \equiv a \pmod m$ for all integers $a$. In the ...
2
votes
1answer
34 views

Can you easily simplify large exponents without Fermat's Little Theorem?

I am asked to check if $x = 19$ is a solution to the following congruence: $$ x^{30034} ≡ 2 \pmod{18}$$ How can I do this? And in general, is there an easy/fast way to solve these types of problems ...
2
votes
0answers
111 views

The congruence $\{(a^m, a^{m+r})\}^\#$ on $a^+$.

I've spent a bit too long on this exercise. It's time to ask for help. This is Exercise 1.20 of Howie's Fundamentals of Semigroup Theory. Let $\rho_{m, r}$ (for $m, r\ge 1$) be the congruence ...
0
votes
1answer
23 views

Combinations of sets raised to the power of a prime modulus

This is a problem out of the text Introduction to the Theory of Numbers by Niven, Zuckerman, and Montogmery and I am having quite a bit of trouble with it. I tried to prove it directly, but that ...
0
votes
2answers
26 views

How can I use the congruence property to determine GCD?

As per my text, the congruence property is: If a > 0, b, and b' are integers such that $$b \equiv b' (mod\ a)$$ then $$(a,b) = (a,b')$$ I'm trying to use that to determine (7,150) and (28,-288). Any ...
4
votes
1answer
133 views

Congruences and pigeons

The question is this: Given $n$ integers, $(a_1, \dotsc, a_n)$, show that there is some subset $B\subseteq \{1,\dotsc, n\}$, such that $$\sum_{i\in B}i \equiv 0 \bmod n.$$ It looks likes this ...
0
votes
1answer
51 views

Can we not apply the Hensel Lifting Lemma in this case?

Check if the equation $x^2=-1 \text{ in } \mathbb{Z}_2$ has a solution, and if it has, calculate the three first positions of the solution. So, we are looking for a solution $\pmod 2$, one solution ...
1
vote
2answers
36 views

Criteria for $p$ being a prime number.

I'm trying to prove the following problem: $p$ is a prime iff for all $n\in \mathbb{Z}$ with $n\not \equiv 0\mod p$, we have $n^{p-1}\equiv 1 \mod p$. The ($\Rightarrow$) direction is easy: we have ...
0
votes
2answers
42 views

Find all integers $k$ such that $k^2\equiv 5k\pmod{15}, 2\leq k\leq 30$.

I want to solve the congruence for $k$ such that $k^2\equiv 5k\pmod {15}, 2\leq k\leq 30$. For this, if $\gcd(15,k)=1$, then $k\equiv 5\pmod{15}$. Is my approach correct? How can I get the values ...
1
vote
1answer
43 views

Number of congruence relations of a 4-element non-cyclic group

How many congruence relations does a 4-element non-cyclic group have? Am I right that I have to find the normal subgroups in order to find the congruence relations? Thanks
1
vote
1answer
32 views

About a new type of congruence system.

If $A\equiv B\pmod m$ then m|(A-B). What if you used a 2 coordinate congruence where $C\equiv D\pmod {m,n}$ then there exists R,S such that (C-D) = m R+n S, where R and S are coprime. So if $A\equiv ...
1
vote
2answers
42 views

Find the least value of $n$ such that $n^{25}\equiv_{83}37$

Let $n\in\mathbb{N}$. Find the least value of $n$ such that $n^{25}\equiv_{83}37$. I concluded that $0<n<83$. Then I wrote $n^{25}$ as $\left(n^5\right)^5$ and let $t=n^5$. Now, it is hard to ...
0
votes
2answers
15 views

Solve using Linear Congruences and Divisibility.

Let r be the common remainder when 1059, 1417 and 2312 are divided by d>1. Find the value of d-r. Find using linear congruences and divisibility.
3
votes
1answer
59 views

A combinatorial conjecture

I'm trying to prove the following conjecture. Conjecture. Let $p \equiv -1\!\pmod{6}$ be a prime, and let $a,b > p$ be integers with $p \nmid ab(a+b)$. Then $$ \sum_{r=0}^{p-3} ...
0
votes
1answer
25 views

Explanation of congruence and modulo

Consider the set $A$ = {${-6, -5 -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12}$} Write down the numbers in $A$ congruent to $1$ modulo $4$. Can someone explain why the answer is not $-4,-1,-4,8,12$ ...
0
votes
1answer
13 views

Congruence modulo n where one side is equal to 1

In the Miller-Rabin test for prime numbers, there is a congruence in the form of $a^{n-1} ≡ 1$ (mod $n$). I'm curious as to how $1$ modulo $n$ cannot just be written as $n$? And the left side ...
2
votes
1answer
28 views

Meaning of congruence notation for Bernoulli Numbers

I am studying Theorem 4(von Staudt's Theorem) in Borevich-Shafarevich's Number Theory(1966)(page 384) which states: Let $p$ be a prime and $m$ an even integer. If $(p-1)\nmid m$, then $B_m$ is ...
1
vote
1answer
38 views

How to figure out congruences involving large numbers?

The one I'm stuck on now is: $$3^{1996001} ≡ 2664001 \mod 3992003$$ Absolutely no idea how to get this! I could whittle it down if I knew the multiplicative order of $3$ modulo $3992003$, but I have ...
2
votes
2answers
31 views

Linear equation over $\mathbb{Z}/n\mathbb{Z}$

For given $a,b\in \mathbb{Z}/n\mathbb{Z}$ is there a criterion which allows one to determine whether there exists $x\in \mathbb{Z}/n\mathbb{Z}$ with $ax=b$?
3
votes
2answers
89 views

The remainder of $1^1+2^2+3^3+\dots+98^{98}$ mod $4$

How can I solve this problem: If the sum $S=(1^1+2^2+3^3+4^4+5^5+6^6...+98^{98})$ is divided by $4$ then what is the remainder? I know that all the even terms I can ignore since ...
1
vote
1answer
34 views

Quadratic congruence $x^2+5x \equiv 12 \pmod{31} $ [closed]

Does $$x^2+5x \equiv 12 \pmod{31} $$ have a solution?
1
vote
0answers
23 views

continuation of thread connected with system of congruences

System of 3 linear congruences I read this subject and I have doubts. Why $x\equiv 25 \pmod{7^2} \implies x\equiv 4\pmod {7} $ ? $x\equiv 399\pmod{1089}$ Is equivalent to system: $x \equiv 399 ...
2
votes
4answers
52 views

system of congruence - my approach

We have: $$k^3 + l^3 \equiv 0 \pmod{17}\\ k^2 + l^2 \equiv 0 \pmod{17} $$ And I get: $$k = 17n+r_k\\ l = 17m+r_l$$ And I analyzed possible rests respect to system of congruences. My result is: $$ ...
4
votes
3answers
73 views

Triangle Congruence

I have found a problem form internet and got stucked trying to proof or disproof it. It says: Given AD=AE ,BF=FC; Proof △ABE≌△ACD Update 1 The @Matrial's solution seems very promising however ...
0
votes
2answers
31 views

Solve equation of second degree - congruence

I have following equation: $$n^2 - n + 2\equiv 0\pmod{49}$$ So I get: $$n^2 - n + 2\equiv 0\pmod{7}$$ The only number is: $$n\equiv 4 \pmod7$$ Thus, I used Hensel's Lemma. And according to (3) point ...
1
vote
1answer
35 views

If $A \equiv 1 \pmod y$ and $A \equiv 1 \pmod {by}$ where $\gcd(b,y)=1$, then $A \equiv 1 \pmod b$?

I am looking at examples where I am coming across the following situation again and again: $A \equiv 1 \pmod y$, $A \equiv 1 \pmod {by}$, where $\gcd(b,y)=1$. Then I am always getting $A \equiv 1 ...
1
vote
1answer
250 views

What is the difference between Congruent and equal?

What is the difference between equal and congruent? When I should say that the two figures are congruent or equal ( identical)? What is the difference between them. Can somebody please explain me with ...
5
votes
2answers
85 views

How many solutions are there for the congruence $x^{14}+x^7+1 \equiv 0 \; (\text{mod } 343)$?

I have another question for you: Tell how many solutions does the congruence $x^{14}+x^7+1 \equiv 0 \; (\text{mod } 343)$ and compute at least one of them. Does this kind of exercise have a ...
2
votes
2answers
74 views

general form in congruence

Could we generalize this example of congruence issue for $x,n \in \mathbb{Z}_*$? $$ 1+x+\cdots + x^{n-1}\equiv n \pmod {x-1} $$
2
votes
2answers
107 views

congruence issue

I need to understand why this : $$(1+4+\ldots+4^{n−1})\equiv n \pmod3$$ Is that because \begin{align} 1&\equiv -2 \pmod3\\ 4&\equiv 1 \pmod3\\ 4^{2}&\equiv1 \pmod3\\ ...
0
votes
2answers
45 views

how to solve to congruence $x^{98}\equiv99\pmod{125}

I show you my attempt: $$(125, 98) = 1 \Rightarrow(x^{98} , 125) = 1 \Rightarrow (x, 125) = 1$$ (Euclidian Algorithm) $$x^{\phi(125)} = x^{100} \equiv1\pmod{125} \wedge x^{98} \equiv99(\mod 125) ...
2
votes
1answer
65 views

About Rees homomorphism

I am came across the notion Rees Congruence for semigroups. J. Howie defines it as $$\rho_I=(I\times I)\cup {1_S}$$ wherein $I$ is an ideal of semigroup $S$ ...
5
votes
2answers
87 views

How to solve the congruence $x^{59} \equiv 604 \pmod{2013}$?

$$x^{59} \equiv 604 \pmod{2013}$$ Could somebody give me any clue? I have no idea how to start. I see that $59$ is prime.
3
votes
2answers
86 views

Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$. I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$. ...
1
vote
2answers
45 views

Proof that the congruence relation on $\mathbb Z$ is transitive (attempt shown)

I have answered this question to the best of my knowledge but somehow I feel as if I am missing something? Can I further prove this statement or add anything to it? Question: Let $m \in \mathbb ...
1
vote
1answer
39 views

Verification of binomial coefficient congruence $\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$

Let $j\ge 1$ be an integer and $p$ prime. Is it true that $$\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$$ My work No, take $j>p$, then the RHS is zero, while the LHS need not be $\equiv 0$. For ...
1
vote
3answers
43 views

If $x$ leaves remainder $2$ when divided by $8$, what will the remainder be when $x + 9$ is divided by $8$?

If the positive integer $x$ leaves a remainder of $2$ when divided by $8$, what will the remainder be when $x + 9$ is divided by $8$? I love to put stuff into algebraic equations to make life ...
0
votes
0answers
25 views

is binomial congruence given in article true or false?

I'm just reading a paper which, on its page 3, Application 8, claims the following: $$\binom{k+sp}{j}\equiv\binom{k}{j}\pmod{p}$$ where $p\ge 1$, $s\ge 1$, $k\ge 1$ and $p\not\mid j$ (actually, it ...