Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $b-a$.

learn more… | top users | synonyms

0
votes
1answer
10 views

Properly discontinuous action on hyperbolic plane

If we have G acts properly discontinuously on hyperbolic plane $\mathbb H$, then for any point p $\in \mathbb H$, exist neighborhood V s.t. gV$\cap$V =$\emptyset$ iff gp$\neq$p. Given this, can we ...
3
votes
2answers
53 views

Determine the number of subgroups of $\Bbb Z_p \times \Bbb Z_p$, where p is prime.

There are some answers online and we got one in our lecture. Unfortunately I have spent several hours trying to make sense of it and getting nowhere. I think it is mainly due to the fact of me being ...
0
votes
2answers
28 views

Exponentiation of big numbers with Euler Theorem

I need to compute $5^{12241} \pmod{13}$ and as suggestion I have that I should use the Euler's theorem. The latter states that whether $a$ is relatively prime to $n$ then $a^{\phi(n)}=1\pmod{n}$. ...
4
votes
4answers
103 views

Let $S = \{n\in\mathbb{N}\mid 133 \text{ divides } 3^n + 1\}$. Find three elements of S.

Question: Let $S = \{n\in\mathbb{N}\mid 133 \;\text{divides} \; 3^n + 1\}$ $a)$ Find three different elements of $S$. $b)$ Prove that $S$ is an infinite set. My intuition is find the prime factors of ...
1
vote
1answer
28 views

Show that that $x^{\varphi(pq)/\gcd(p-1,q-1)}\equiv 1\mod pq$ for all $x\in (\mathbb Z/pq\mathbb Z)^\times$

If $p$ and $q$ are distinct odd primes, how could I approach showing that $x^{\varphi(pq)/\gcd(p-1,q-1)}\equiv 1\pmod {pq}$ for all $x\in (\mathbb Z/pq\mathbb Z)^\times$? I understand that ...
1
vote
3answers
32 views

Solve $22t \equiv 9 \pmod{7}$

I am trying to solve a modular arithmetic system and I got to the point where I have to solve $22t \equiv 9 \pmod{7}$ for $t$. I researched on the internet and found that there are many ways to solve ...
1
vote
3answers
78 views

Find all primes $p,q$ and even $n > 2$ such that $p^n+p^{n-1}+\cdots+1 = q^2+q+1$

Find all primes $p,q$ and even $n > 2$ such that $p^n+p^{n-1}+\cdots+1 = q^2+q+1$. Attempt The first thing I would do is simplify the geometric series to $\dfrac{p^{n+1}-1}{p-1} = q^2+q+1$. I ...
0
votes
0answers
12 views

Prove that the mean of the $u_i$'s generated by a congruential linear generator of complete period is $\frac{1}{2} -\frac{1}{2m}$

Congruential linear generator (pseudo random numbers) I have to prove this proposition but I don't know how. I tried by induction on $m$, the modulus of the generator, but it hadn't got me anywhere: ...
2
votes
1answer
23 views

Modular arithmetic system $x \equiv 2 \pmod{7}$ and $x \equiv -5 \pmod{22}$

The task is to find all integers $x$ such that $x \equiv 2\pmod 7$ $x \equiv -5\pmod {22}$ My guess is that the Chinese Remainder Theorem may help. I've never done a question like this that had a ...
0
votes
0answers
34 views

Show that Z*n is the maximal subset of Zn which is a group with the operation [a] · [b] = [ab].

Let Zn be the set of equivalence class of integers mod(n) which are relatively prime to n, i.e. Zn = 􏰀[i] | gcd(n, i) = 1􏰁. So I understand how this works when the binary operation is ...
0
votes
1answer
20 views

If $a\equiv b \pmod{p_i}$ for $i=1,2,…,k$ then prove $a\equiv b \pmod{p_1p_2\cdots p_k}$

If $a\equiv b \pmod{p_i}$ for $i=1,2,\cdots,k$ then prove $a\equiv b \pmod{ p_1p_2\cdots p_k}$ $a\equiv b \pmod{p_1}$ implies $a-b=p_1x_1$ Similarly, $a-b=p_2x_2,\ \cdots,\ a-b=p_kx_k$ So, ...
0
votes
1answer
23 views

Using Modulo reduction

I'm really confused on how to do modular reduction. I understand we're supposed to take the factor of the exponent? for example how would I go about doing modular reduction on: $5^{17}$ mod 16
1
vote
2answers
37 views

I don't understand a step in the proof of Euler's Theorem, please explain

I am trying to learn the proof for Euler's theorem which states: If $\gcd(a,m)=1$ then $a^{\phi(m)} \equiv 1 \mod m$. The proof goes like this. Take the reduced residue system modulo $m$. ...
0
votes
2answers
23 views

Showing Modulo Congruence Amongst Prime Divisors (Number Theory)

I'm having trouble figuring out how to show the general existence part of the following problem. Suppose $n\in\{1,2,3...\}$ and $n\equiv 7\mod{10}$. Show that $\exists$ a prime divisor $p$ of $n$ ...
0
votes
0answers
11 views

Name of that extension of modular inverse?

The modular inverse is a well-defined involution over $\mathbb Z_n^*$: when $\gcd(x,n)=1$, the inverse of $x$ modulo $n$, noted $x^{-1}\bmod n$, is the single integer $z$ with $x\cdot z\equiv1\pmod n$ ...
0
votes
3answers
24 views

What to do if the modulus is not coprime in the Chinese remainder theorem?

Chinese remainder theorem dictates that there is a unique solution if the congruence have coprime modulus. However, what if they are not coprime, and you can't simplify further? E.g. If I have to ...
3
votes
4answers
115 views

Remainder when ${45^{17}}^{17}$ is divided by 204

Find the remainder when ${45^{17^{17}}}$ is divided by 204 I tried using congruence modulo. But I am not able to express it in the form of $a\equiv b\pmod{204}$. $204=2^2\cdot 3\cdot 17$
0
votes
1answer
18 views

What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26.

What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26. I figured that the matrix is only invertible if its determinant and the n value 26 's gcd is 1, meaning they are ...
0
votes
2answers
33 views

Find a solution $x\in\mathbb{Z_{\mathrm{784}}}$ for $x\cdot\overline{602}=\overline{308}$

I know that I have to find a positive integer $x$ that I can multiply with $602$ and then divide the result by $784$ so that the remainder of that integer division is $308$. I am sure that this is ...
0
votes
2answers
40 views

Solve the following congruence: $x(x+1)(x+2) \equiv 0 \pmod{221}$

Find the first five solutions for, $$x(x+1)(x+2) \equiv 0 \pmod{221}$$ I am very confused. By CRT, $x(x+1)(x+2) \equiv 0 \pmod{13}$ and $x(x+1)(x+2) \equiv 0 \pmod{17}$ But these two ...
4
votes
2answers
84 views

Last digit of $235!^{69}$

Problem What is the last digit of $235!^{69}$? It's been far too long since I did any modulo calcuations, and even then, the factorial would set me back. My initial thought goes to the last digit ...
0
votes
5answers
58 views

How can I prove that $\frac{21n -3}{4}$ and $\frac{15n+2}{4}$ are never both integers?

I have converted this to a problem of modular arithmetic. I seek to prove that $21n-3$ and $15n+2$ are never congruent to $0\pmod 4$ for the same value of $n$. I observed that $21n$ is ...
2
votes
0answers
70 views

Show that the equation $x^2+y^2+z^2= (x-y)(y-z)(z-x)$ has infinitely many solutions in integers $x, y, z$.

Show that the equation $x^2+y^2+z^2= (x-y)(y-z)(z-x)$ has in finitely many solutions in integers $x, y, z$. It seems like if I find a set of $x,y,z$ that satisfy this for any values that will ...
0
votes
0answers
8 views

Stabilizer of a point in R$\cup \infty$ in a discrete subgroup $\Gamma \subset SL_2(R)$

Let $\Gamma $ be a discrete subgroup of $SL_2(R)$. Let $\Gamma_z$={$\gamma \in \Gamma : \gamma(z)=z$}. Let $Z_{\Gamma}$={$\pm I\cap \Gamma$}. Then how to prove for z $\in R\cup \infty$, $\Gamma_z ...
1
vote
1answer
21 views

$A(n) = f(m)$ numbers of $f(m)$ followed by $f(m)$ numbers of $0$. $f(m)$ is the remainder when $m$ is divided by $9$.

A series is formed in the following manner: $A(1) = 1; $ $A(n) = f(m)$ numbers of $f(m)$ followed by $f(m)$ numbers of $0$; $m$ is the number of digits in $A(n-1).$ Find $A(30)$. Here ...
1
vote
2answers
26 views

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$. I am able to work out the solution using Euclidean algorithm techniques, but the signs on the expression do not match up with the initial ...
1
vote
1answer
24 views
1
vote
1answer
36 views

Last 3 digits of Marsenne numbers

Marsenne numbers are of the form $2^{p} - 1$, $p$ is a prime. Last $3$ digits can be obtained from $2^{p} - 1 \equiv x \pmod {1000}$. This is equivalent to $$2^{p} - 1 \equiv x_1 \pmod 8\tag1$$ and ...
0
votes
1answer
23 views

Modulus Notation Division

I have a couple of silly questions (it will definitely demonstrate my lack of ability in mathematics :P) Is there a type of reduction or absorption of modulus in congruence equations? Here's an ...
2
votes
1answer
74 views

How does one prove that $2\uparrow\uparrow16+1$ is composite?

Just to be clear, close observation will show that this is not the Fermat numbers. I was reading some things (link) when I came across the footnote on page 21, which states the following: ...
2
votes
3answers
45 views

Sum of all elements in congruence class modulo n

With $+$ defined as $[a]+[b]=[a+b]$, show that $[0]+[1]+\cdots+[n-1]$ is equal to either $[0]$ or $[n/2]$ in $\Bbb Z_n$. How do I go about proving this? I have managed to get $[(n^2-n)/2]$ using the ...
0
votes
3answers
72 views

Remainder of $98!$ modulo $101$

My question is: What would be the remainder when $98!$ would be divided by $101$? Though this question is very easy but I'm a little confused about my concepts. I have found multiples of $2$ and ...
1
vote
0answers
12 views

Number of Solutions to a Linear Equation Mod N

Is there a formula for the number of solutions to $$a_1x_1+\dots+a_nx_n \equiv 0 \mod{N}$$ such that $(x_i,N)=1$ in terms of the coefficients $a_1,\dots,a_n$? Clearly, by Chinese Remainder Theorem, ...
1
vote
2answers
60 views

$11^{-1}$ modulo $91$ is $58$. Why?

I am reading wiki article about Quadratic Sieve and it says $11^{-1}$ modulo $91$ is $58$ Why? How is it been calculated?
5
votes
1answer
43 views

Modular Arithmetic - summing from 1 to a prime

Apologises for the vague title; I couldn't think of anything better to call it. I'm currently working on the following question: Consider the equation $\sum_{i=1}^{5} \frac{1}{i} = \frac{X}{5Y}$. ...
1
vote
2answers
34 views

Is there a difference between modulo groups with and without asterisks ($\mathbb{Z}_{38}$ vs $\mathbb{Z}_{38}^*$)?

I know modulo group $\mathbb{Z}_{38}$ but I saw it with a star in some question: $\mathbb{Z}_{38}^*$. Is it is the same as $\mathbb{Z}_{38}$ or a different group? If it refers to the same group does ...
-1
votes
0answers
31 views

Do $p=2617$ and $q=3571$ have modular multiplicative inverse with $e = 17$?

I need multiplicative inverse of $17 \mod \left(\phi(p) \cdot \phi(q)\right)$. They are both prime, the totient of the product is $2616 \cdot 3570 = 9339120$. But $17$ is a factor of $9339120$, ...
0
votes
1answer
20 views

Sum of the squares of $5$ consecutive positive numbers can not be a perfect square.

Proof that, Sum of the squares of $5$ consecutive positive numbers can not be a perfect square. As far I did, $(n-2)^2 + (n-1)^2+n^2 + (n+1^2) + (n+2)^2$ $=2(n^2+4) + 2(n^2 + 1) + n^2$ $=5(n^2 + ...
0
votes
5answers
51 views

Is the following proof correct for $n(n+1)(n+5) = 3X$

The objective is to prove that $n(n+1)(n+5)$ is a multiple of 3. I took the following simplistic route $$n(n+1)(n+5) = 3X$$ $$n(n+1)(n+5)\frac{n+2}{n}\frac{n+6}{n+5} = ...
0
votes
0answers
10 views

Using Modulo to calculate number of days to a certain date

I'm trying to create a function that, given today's date and the date of a holiday in day-of-the-year format, returns the number of days between today's date and the date of a holiday. (Day of the ...
1
vote
0answers
28 views

Modular and prime prove [duplicate]

Suppose that $p$ is prime and $p=n^2 +5$ for some natural number $n$, prove that the final digit of $p$ is equal to $1$ or $9$ which is $p=1(mod10)$ or $p=9(mod10)$ What I have to tried so far: in ...
0
votes
1answer
24 views

How can I find the exponent of a power of two from its remainder modulo a power of three?

Suppose that ${2^m}\equiv k\pmod {3^n}$ and that I know $n$ and $k$. Is there a way to find the lowest (or indeed any) value for $m$ other than by enumerating the possibilities? Note: I'm aware that ...
1
vote
1answer
41 views

Find last two digits using modular arithmetic [duplicate]

Find the last two digits of $7^{7^{7^{10217}}}$. We need to find $7^{7^{7^{10217}}}$ (mod $100$) and $\phi(100) = 40$ So $7^{40} \equiv 1$(mod$100$) I don't know how to proceed after this
0
votes
1answer
33 views

Modular exponentiation and two primes

Given two primes $11$ and $5$, find all $\alpha> 1$ such that $$\alpha^{5} \equiv 1 \pmod{11}$$ What theorem will help me to find it out?
0
votes
1answer
16 views

an array A[1..N] how many indexes (i,j) are there such that cumulative sum(i,j)%K = 0?

Lets say I have an array A[x1,x2,x3,...xN] of size N. for N = 4 , A = {x1,x2,x3,x4}. [1 based index] Now,I have to tell how many tuples (i,j) are there such that i<=j and cumulative sum(i,j) is ...
0
votes
2answers
52 views

Solving modulo equations with one variable

Given the following equation: $$10 = 4^x \pmod {18}$$ How can one know what are the correct values for $x$ ?
1
vote
1answer
38 views

How many non-negative integers less than $10000$ are there such that…

I am stuck with the following two problems : How many non-negative integers less than $10000$ are there such that the sum of digits of the number is divisible by $3$ ? The options are : ...
0
votes
0answers
19 views

Calculate large modulus by hand

I want to calculate 920^17 mod 2773. I get 1701 as answer. The answer is 948 in the textbook. It does not explain how to get it. I am using this method: 17 = 1 + 16 (powers of 2) 920^1 mod 2773 = ...
1
vote
0answers
14 views

Cracking any linear congruential generator

I have a linear congruential generator $X_{n+1} = (aX_n + b) \bmod 2^k $with given arguments and number $Y$. The problem is to find the smallest $i$ that $X_i = Y$ or tell that there is no such $i$. ...
3
votes
2answers
40 views

Primitive Root Mod P

I have been able to answer all of the parts to the question apart from part (v). Any tips on how? I assume I have to show that $ m=2^n $, but I am unsure as to how. I can't imagine it is very ...