As of May 31, 2023, we have updated our Code of Conduct.

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

10,941 questions
Filter by
Sorted by
Tagged with
45 views

### Proof of the general case for Fermat's little theorem

I have proved Fermat's little theorem (F.L.T) that is "If $p$ be a prime, then $x^p=x\bmod p$ " by induction on x for $x \in \mathbb Z$ and $x \ge 0$. I want to prove the general case that ...
16 views

### Find divisors using congruences

We have $n := 115921$ , $2^{\frac{n-1}{4}} \equiv 963 \pmod{n}$, and $2^{\frac{n-1}{2}} \equiv 1 \pmod{n}$. How would you calculate a divisor of $n$ and why will the method work correctly (...
1 vote
60 views

1 vote
49 views

### What is the minimum modulus where the first $n$ values of Fibonacci sequence are still unique?

Using the sequence $F_1 = 1, F_2 = 2, F_n = F_{n-1} + F_{n-2}$ $$1, 2, 3, 5, 8, 13, \ldots$$ What is the smallest modulus $M$ for each $n$ such that this sequence $S_n = F_n \mod M$ has no ...
49 views

### Diagonalizing matrices over $\mathbb{Z}/ p^k$

Let $p$ be an odd prime and $A$ a symmetric matrix in $M_{n\times n}(\mathbb{Z}/ p^k)$. How does one prove there exists a matrix $M \in GL_n(\mathbb{Z}/ p^k)$ such that $M^tAM$ is diagonal? I do not ...
56 views

### Finding prime numbers with mod function with respect to given odd number $'a'$ between $2^n$ and $2^{n+1}$

Here are few steps which made sense when analysing the prime numbers Step 1: For any odd number "$a \in Z^+$" e.g. 17 Step 2 : $a$ is $2^{n} < a < 2^{n+1}$ Step 3: now get the list ...
54 views

173 views

25 views

### Novice question regarding Rivest Shamir Wagner Time Lock Puzzles of the form $x^{2^t} \bmod N$ with $N=p.q$ primes.

I'm using the Rivest Shamir Wagner Time Lock Puzzle setup in an application. The puzzles are of the form: $x^{2^t} \bmod N$ with $N=p.q$ and p and q are primes. My question is this: assuming I ...