We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [modular-arithmetic]

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

9,820 questions
Filter by
Sorted by
Tagged with
19 views

### Modular arithmetic with symbolic variables in MATLAB

How can I use modular arithmetic on a matrix that has symbolic variables? I want the coefficients of polynomials in t and 1/t to be mod 2. syms t mod( [t^2-1/t-t,-1/t^2;t^2,0],2) gives me FAIL. ...
62 views

33 views

### Groups with the subtraction operation

Why do integer mod integer sets with the operation of subtraction not form groups? For example, integers mod 3 is {0,1,2}, which has an identity (0) and inverses (self inverses). And subtraction is ...
33 views

### Checking a result obtained by Chinese Remainder Theorem

I have the following two linear congruences: $$x \equiv 3 + n\mod p_1$$ $$x \equiv 3 - n\mod p_2$$ where $p_1$ and $p_2$ are distinct primes, and $n$ is the difference between those primes. Does ...
59 views

### Use Wilson's Theorem to show $(q!)^2+(-1)^q \equiv 0$ mod p

Let $q=\frac{p-1}{2}$ and $p$ is an odd prime. Show that $$(q!)^2+(-1)^q\equiv 0\:\:\text{mod p}$$ After searching for a while, I couldn't find this specific congurence question. So therefore I am ...
31 views

45 views

39 views

### Proof that if $\gcd(a,n) = 1$, then $a^k \equiv a^{k \pmod{\phi(n)}} \pmod n$

From Euler's theorem I know that $a^{\phi(n)} \equiv 1 \pmod n$ if $\gcd(a,n) = 1$. However I can't find any proof/explaination of the proof in the title.
67 views

### What are the elements of the modular ring mod 7?

Just getting started with modular arithmetic. Are the elements of a modular ring simply the set of all the numbers from $1$ to $p-1$? in this case $p-1 = 6$ ?
220 views

### A hard question in number theory

Prove that for every natural number $n$, there is a set $S$ of $n$ natural numbers such that for any two different numbers $a,b$ From $S$ the number $a-b$ divides $a$ and $b$ and no another number ...
83 views

### Given two primes $p$, $q$ and their product $pq$, find $\phi(pq)$ mod $p + q$

This is actually from a past year exam question for a computer security module, which I am doing to prepare for my upcoming test. The question provides $pq = 1669806207577$ (for ease of reference, I ...
89 views

### Counting primes in residue classes

Suppose you are sorting all of the prime numbers between $1$ and some large number $N$, from smallest to largest; into buckets which correspond to their residue classes modulo some prime $p_i$. Now ...
68 views

### Proof that $3^{10^n}\equiv 1\pmod{10^n},\, n\ge 2$

This should be rather straightforward, but the goal is to prove that $$3^{10^n}\equiv 1\pmod{10^n},\, n\ge 2.$$ A possibility is to use \begin{align*}3^{10^{n+1}}-1&=\left(3^{10^n}-1\right)\left(...
82 views

### Prove that $2x^3+3x^2+x$ is always divisible by 6 if x is an integer. [duplicate]

Prove that $2x^3+3x^2+x$ is always divisible by $6$ if $x$ is an integer. I started by factoring the expression: $x(2x^2+3x+1)=x(2x+1)(x+1)$ However I wasn’t sure how to progress from here to prove ...
20 views

### Determine a criterion for divisibility by $7$, and uuse it to determine the reminder of the number $12345678923$ when divided by $7$ [duplicate]

I am not sure how i would start this. It would be something mod $7$ but i don't know where to go from there
46 views

### Given integers $m$ and $1 \lt a \lt m$, with $a \vert m$, prove that the equation $ax\equiv 1\pmod{m}$ has no solution.

Given integers $m$ and $1 \lt a \lt m$, with $a \vert m$, prove that the equation $ax\equiv 1\pmod{m}$ has no solution. (That is, if $m$ is composite, and $a$ is a factor of $m$ then $a$ has no ...