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

Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $a-b$. In modular arithmetic, one can add, subtract, multiply, and exponentiate but not divide in general. The Euclidean Algorithm, the Chinese Remainder Theorem, and Fermat's Little Theorem are important throughout mathematics. Modular exponentiation plays an important role in cryptography nowadays.

11320 questions
0
votes
0 answers

Solving modular quadratic equations for beginners

I'm trying to implement something in my program that requires solving modular equations with large numbers. I've seen two types of solution: those that require using trial and error to make the solution to the quadratic "fit" the modulus (which I…
0
votes
2 answers

Show that $29^{41}+41^{29}$ is divisible by 35

How con I Show that $29^{41}+41^{29}$ is divisible by 35. attempt: I think it shouldn’t be difficult but not sure how to prove it. 29 is not a multiple of 5 nor of 7 same for 41.
Valent
  • 3,228
  • 1
  • 15
  • 28
0
votes
0 answers

A congruence lemma, do I need the chinese reminder theorem?

I am trying to prove the next statement. For $r$ different primes such that the product $p_{1}\cdot p_{2}\cdots p_{k}>n^{2}$ and $a,b\in \{-n^{2},...,n^{2}\}$ $a=b \iff \forall r : a \mod p_{r}=b \mod p_{r}$ I made a table to build a numbering…
0
votes
0 answers

Solution of the congruence $103a\equiv 1\mod 101$?

How do I find a solution to the congruence $103a\equiv 1\mod 101$?
0
votes
1 answer

Distribution of Modular Expressions

This is really a programming question that I'm unable to solve because of a math question. I'm having a problem understanding the rules of distribution with modular arithmetic. I have two expressions: a = q mod c + (n - 1) mod c b = q mod c - (n -…
User4407
  • 455
0
votes
0 answers

$\sum_{k=0}^{n-1}(5^k)$ divide 13 only if $5^n-1$ divide 13, with n in $\mathbb{N}$

$\sum_{k=0}^{n-1}(5^k)$ divide 13 only if $5^n-1$ divide 13, with n in $\mathbb{N*}$ I proved that $5^n$ is prime with 13 (n in $\mathbb{N}$) we have: 13 divide $5^n$-1 $\Rightarrow (13 * \sum_{k=0}^{n-1}(5^k)$) divide $(5^n-1) *…
0
votes
1 answer

Understanding Modular Multiplication

I'm reading a book on Cryptography and in the book it explains: A modular multiplication is quite natural to define over such a set of numbers. Let’s take the following multiplication, for example: 3 x 2 = 6 With what you learned above, you know…
preston
  • 101
  • 1
0
votes
0 answers

Why is $P^{ed} \bmod N = P^{1} \bmod N$ if $e$ and $d$ are modular inverses of $\phi(N)$.

Let $d$ be the inverse of $e \bmod \phi(N)$. Therefore, $de \equiv 1 \pmod{\phi(N)} $ $d \equiv e^{-1} \pmod{\phi(N)} $ In RSA encryption, we can decrypt messages because $P^{ed} \bmod N = P^{1} \bmod N$ I don't understand why $P^{ed} \bmod N =…
0
votes
1 answer

How does $(x^{ed} - x) $mod n $= 0$ simplify to $((x^e)^d) $mod $n = x$

I'm trying to follow this proof about RSA n is the product of two distinct primes. $ e * d$ mod $\phi(n)$ = 1 with $ e,d \in \Bbb{N}$ In the last line how does $(x^{ed} - x) $mod n $= 0$ simplify to $((x^e)^d) $mod $n = x$ from script (also meaning…
0
votes
0 answers

How to approach modular arithmetic problem

Let p, q and A be three positive integers. I have the following equation: $$(A mod p) mod q = (A mod q)mod p$$ Find all the ordered pairs $(p, q)$ which satisfy the above equation such that $$1 <=p < q <= N$$ and $N$ <= $10^7$, $A<=10^7$. My…
taurus05
  • 159
0
votes
2 answers

In $Z_{12}$, find non-zero elements $a,b,c$ with $ab = ac$ but $b$ does not equal $c$

In $\mathbb{Z}_{12}$, find non-zero elements $a$, $b$, $c$ with $ab = ac$ but $b \neq c$ $\mathbb{Z}_{12}\setminus \{0\} = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$ I have at the moment that $a = 2, b = 6$ and $c = 4$ $2 \times 6 \equiv 0 \pmod…
user918654
0
votes
2 answers

Congruent Modulo with negative

Given $16 \equiv 7 \pmod m$. Find $m$: $$7-16 = -9$$ so, the $m$ can be what ever can divide into $-9$ ?
MethodManX
  • 1,127
0
votes
0 answers

Calculate all solutions of non linear congruence

Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^{p}-a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as $$ a^{p} \equiv a \quad(\bmod p) $$ Using Little…
0
votes
2 answers

If $a \equiv b\pmod{m^2}$, then prove $ a \equiv b\pmod{m}$

How would I go about proving $$ a \equiv b\pmod{m}$$ given $$ a \equiv b\pmod{m^2} $$ I suspected this was false, so I tried to find a counterexample using a program, and there does not appear to be a counterexample for $m$ in (2, 16). What I have…
bren
  • 171
0
votes
1 answer

Given step size, starting point, and a modulus, how many steps does it take to reach b mod m?

Let's start with a modulus $m=5$ (this could be any integer) a step size $s=2$ (this must be relatively prime with $m$), and an initial starting value modulo $m$ of $i=1$. In this particular case, we have: m: 0 1 2 3 4 x When we advance…
Adam
  • 679