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

4
votes
3answers
93 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
43 views

Computation of large powers

How do I check if $2^{123456789}$ is divisible by 9? I tried using modular exponentiation but it is way too tedious. Is there an easier or faster way to solve it? Thanks!
0
votes
1answer
25 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}$. ...
1
vote
2answers
63 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
1answer
361 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
1
vote
1answer
26 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
31 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 ...
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
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: ...
3
votes
5answers
99 views

What will be the remainder when $2^{31}$ is divided by $5$?

The question is given in the title: Find the remainder when $2^{31}$ is divided by $5$. My friend explained me this way: $2^2$ gives $-1$ remainder. So, any power of $2^2$ will give ...
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$ ...
3
votes
2answers
36 views

Good description of orbits of upper half plane under $SL_2 (Z)$

It's known that $SL_2(Z)$ acts on $H=\{z\, |\, Im(z)>0\}$, is there a good description of orbits of $i$ and $w$, other than directly write down $=\{ \frac{ac|z|^2+bc\bar z+adz+bd}{c^2|z|^2+dc\bar z ...
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
111 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
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 ...
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
39 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 ...
0
votes
2answers
32 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 ...
4
votes
2answers
83 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 ...
13
votes
17answers
10k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
2
votes
0answers
69 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 ...
6
votes
2answers
175 views

Last digits of power towers $7$, $7^7$, $7^{7^7}$, $7^{7^{7^7}}$, … don't change, and generalisation

While playing around with Wolfram Alpha, I noticed that the last four digits of $7^{7^{7^{7^7}}}, 7^{7^{7^{7^{7^7}}}},$ and $7^{7^{7^{7^{7^{7^7}}}}}$were all $2343$. In fact, the number of sevens did ...
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
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
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
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 ...
7
votes
2answers
123 views

Prove that if $7^n-3^n$ is divisible by $n>1$, then $n$ must be even.

I tried using factorization of $a^n-b^n$ for odd $n$ in an attempt to work through to a situation where the factors are such that they cannot have n as a factor. But I reached nowhere. Here's how I ...
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
1answer
46 views

Possible dividers of a number of three digits

For each natural number $n$ of $3$ decimal digits (thus with the first non-zero digit), we consider the number $n_0$ obtained by eliminating its possible digit equal to zero. For example, if $n = ...
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?
-1
votes
0answers
30 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$, ...
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 ...
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}$. ...
0
votes
1answer
53 views

Calculating the summation of n mod i

This is a codeforces question (link), where we have to calculate the summation of N mod i where i goes from 1 to M. N and M are very large values 10^13. They have provided an editorial for this ...
0
votes
1answer
459 views

Dividing the linear congruence equations

$$42x \equiv 12 \pmod {90}$$ This is a pretty simple congruence equation. $\gcd(42,90)=6$; $6|12 \implies $ a solutions exists. I've always been solving congruence equations with that scheme: ...
27
votes
2answers
712 views

Fibonacci $\equiv -1 \mod p^2$

Is there a prime $p > 3$ such that the Fibonacci number $F_{np} \equiv -1 \mod p^2$ for some natural number $n$? I know none of the first $1000$ primes $> 3$ qualify. EDIT: In response to ...
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 ...