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
1
vote
1 answer

General divisibility test for $p\in\mathbb{N}$, $p$ prime

I have read the recursive divisibility test of number $n\in\mathbb{N}$ as $$f-Mr,$$ where $f$ are the front digits of $n$, $r$ is the rear digit of $n$ and $M$ is some multiplier. And I want to see if $n$ is divisible by some prime $p$. I saw that…
1
vote
4 answers

How to determine all the invertible elements?

I have this excercise, I need your help on the third point: i) Determine two integers $\alpha$ and $\beta$ such that $12\alpha + 7\beta = 1$ Answer: $\alpha = 3$ and $\beta = -5$ ii) Determine all the solutions of $$7x\equiv 1 (mod. 12)$$ Answer:…
BAD_SEED
  • 463
1
vote
0 answers

Euler's totient function - Why?

I know this one's true, but I can't prove it. I've tried everything. $$a^{b\bmod{(\theta(m))}}\bmod(m)=a^b\bmod(m)$$ Multiply the exponent with $m-1$ (assume $m$ is prime, it doesn't matter anymore) and it's opposite, but opposite where? the…
1
vote
1 answer

Modular arithmetic - Power

I am dealing with the following question: Given a,b,c,d, p positive integers, I wanna compute a^(b^(c^d)) mod 2p+1. Given that p is sophie-germain. That is, 2p+1 is also prime. Any ideas?
1
vote
2 answers

Modular Arithmetic and Congruences

I understand that $a \equiv b \pmod n$ means when you divide each $a$ and $b$ by $n$ you get the same remainder. But why do people say: "$a$ divided by $n$ gives you remainder $b$"? They say that in the first 30 seconds of this video lecture…
rubixibuc
  • 125
1
vote
0 answers

First ODD primes and modular equation

This is a modular equation involving first $k$ ODD primes: $$ 3^{5+7+11+13+17+\dotsb+p(k-3)+p(k-2)}=p(k-1) \mod p(k) $$ where $p(k)$ is the $k$-th ODD prime number. I've checked $k$ up to $50$, but the only solution I've found is for $k=20$. Are…
1
vote
2 answers

Finding inverse of $2\mod 127$?

I can't seem to understand why the inverse of $2 \mod 127=64$ I used the Euclidean algorithm: $2x=1 \mod127$ $127=63\cdot 2+1$ $1=127-63\cdot 2 \mod127$ $x=63$? I'm pretty sure it's a really stupid error....please help!
1
vote
1 answer

GCD Proof with Unique inverses

I'm given a problem stating: If $\gcd(m,x) = 1$ then $x$ has a unique inverse modulo $m$. I'm told to state and prove the converse, which I believe is: $$ x \text{ has a unique inverse modulo } m \implies \gcd( m, x ) = 1$$ After that step I'm…
1
vote
1 answer

Question on Modular Arithmetic proof

From my textbook I am really confused. The only numbers this works for are multiples of 10, and 11. 10 mod 3 is 1, yes, but 12 mod 3 is 0! Any idea on how to answer this question? It makes no sense to me.
1
vote
1 answer

Natural numbers raised to phi function

Let $a$ and $b$ be relatively prime natural numbers greater than or equal to 2. Prove that $a^{\phi(b)} + b^{\phi(a)} = 1 \quad \pmod {ab}$. The only equations I know with $\phi$ are $a^{\phi(m)} = 1 \pmod m,$ when $a$ and $m$ are relatively…
1
vote
2 answers

General method to solve a modular system

I noticed that if we got a system of modular equations that all equals to $0$ we can always solve the system; for example in a system like this: $$\begin{cases}n \mod m =0 \\n \mod m' =0 \\n \mod m'' = 0 \end{cases} \tag 1$$ $$n=\text{LCM}\…
PunkZebra
  • 1,595
1
vote
3 answers

Proving a particular divisibility rule for 7

I came across this rule of divisibility by 7: Let N be a positive integer. Partition N into a collection of 3-digit numbers from the right (d3d2d1, d6d5d4, ...). N is divisible by 7 if, and only if, the alternating sum S = d3d2d1 - d6d5d4 + d9d8d7…
user207710
1
vote
2 answers

Baby Step Giant Step Algorithm

I'm currently trying to figure out how the Baby Step Giant Step algorithm works and there's a step which I don't really understand. (You can see it here: http://en.wikipedia.org/wiki/Baby_step_giant_step) Basically, its step 3. where you calculate…
ysl208
  • 11
  • 1
  • 2
1
vote
1 answer

'Distributive' property for a function mod m

What properties must some function $f(n)$ have for it to be the case that: $f(n) = (n + 3) \mod m = (n \mod m) + (3 \mod m)$? Similarly, what if $f(n) = (n + 3) \mod m = (n \mod m + 3)?$ Is this something that is well studied? Where might I go to…
1
vote
3 answers

$24x^7 + 5y^2 = 15$ has no integer solutions, having none $\!\bmod 12$

Prove $5a^2\equiv k \pmod{12}$, where $k\in \{0,5,8,9\}$. Hence show that the equation $24x^7 + 5y^2 = 15$ has no integer solutions. My lecturer used a table containing $a$, $a^2$, and $5a^2$ from $1$ to $11$ to which he applied $\pmod{12}$ for…
Mondli.K
  • 393