# Tagged Questions

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$.

49 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 ...
101 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 ...
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}$. ...
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!
66 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 ...
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 ...
27 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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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, ...
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
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$. ...
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$ ...
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$ ...
36 views

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 ...
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 ...
24 views

### What is the number of $0\leq j_1, j_2, \ldots, j_n\leq v-1$ such that $\sum_{i=1}^{n}j_i\equiv 0 \mod v$?

In the title, $v$ is an integer such that $v>1$.
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 ...
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 ...
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 ...
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: ...
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 ...
46 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} = ...