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

Modular Exponentiation when only mod of a value is known

I am trying to calculate $A^A$ % mod, where mod is $10^9 + 7$. I can calculate ($A$ % mod) for any value of mod but don't have direct access to A. How would I solve this?
Omar S
  • 105
0
votes
1 answer

Finding remainders from an encoding function

Let's consider the encoding function: $$y=ax \bmod 5$$ where $x$ is the number that corresponds to a certain letter in the alphabet. I'm trying to understand why for every number $n$, with $n>4$, I can find a number a such as $ax \equiv nx \bmod…
AleWolf
  • 185
0
votes
1 answer

How to solve the congruence equation $6x+y \equiv 19 \pmod {26}$?

I have the congruence equation: $$6x+y \equiv 19 \pmod{26}$$ One way to solve it is to start from: $$y \equiv 19-6x \space \pmod{26}$$ and try all the $y\in \left \{ 0,\dots,25 \right \}$. However my book states that there exist only $12$…
AleWolf
  • 185
0
votes
3 answers

Find multiplicative inverse when numbers are not coprime

I want to calculate the value of $a$, given the equation: $-8a\equiv 12 \mod26$ I know that i have to find the multiplicative inverse of $-8$, but since $\gcd(-8,26) \neq 1$, I suspect there can be 0 or many multiplicative inverses. Is this true ? I…
AleWolf
  • 185
0
votes
2 answers

CRT- adding numbers in two different mod worlds

The proof of the CRT goes as follows: Given the number $x \epsilon Z_m$, $m=m_1m_2...m_k$ $$M_k = m/m_k$$ construct: $$ x = a_1M_1y_1+a_2M_2y_2+...+a_nM_ny_n$$ where $y_k$ is the particular inverse of $M_k\ mod\ m_k$ $$\Rightarrow x\equiv…
0
votes
2 answers

Modular Arithmetic Substitution Problem in Multiplication

99 ≡ 387,420,489 ≡ 5 (mod 22) However I have tried to reach this result using the following steps and I got it wrong: 99 ≡ 93 x 93 x 93 ≡ 729 x 729 x 729 ≡ 3 x 3 x 3 ≡ 18 (mod 22) I can use this substitution in sum operations, but is it correct to…
0
votes
2 answers

Delimit the modulus of an unknown modular arithmetic

Suppose we have a function $f(n) = 1$ when $n \equiv x mod M$ and $0$ otherwise, but I don't know $M$. Also suppose I know $f = 0$ for a subset of $q$ natural numbers. How I can delimit $M$? That is, $M > m1$. There are exist a known algorithm fo…
Alnair
  • 141
0
votes
3 answers

$6x + 13 = 7 \pmod{24}$

$6x + 13 = 7 \pmod{24}$ What method can I use to solve this problem? I tried with the method I used here but it won't work because I can't use Euclidean algorithm on this problem.
0
votes
1 answer

If $p=4k+3$ is prime then exist $x$, $y\in\mathbb{Z}$ such that $p| (x^2+y^2+1)$

i have an exam test question in arithmetic: If $p=4k+3$ is prime then exist $x$, $y\in\mathbb{Z}$ such that $p| (x^2+y^2+1)$. Is that anyway to prove this?
Hoàng
  • 301
0
votes
1 answer

Change of approach in modular arithmetic algorithm?

So I'm taking an intro-Math course for CS. We are currently covering modular arithmetics. My professor was explaining calculating the mod of large numbers, such as 163^42 Mod 49 in this case. First, she decided to solve for 16^42 instead because…
0
votes
0 answers

Mod Magic Trick for 8

The question is: Find the mod magic trick for 8. Explain why your trick works and describe you answer using a nine digit number: abcdefghi. So what I have figured out is that the mod trick for 8 is to reduce the last 3 digits in mod 8 to get the…
0
votes
0 answers

Mega-modular exponentiation

How can I find the answer of this type of modular exponentiation? Here, one thing should be noticed, that is 'MOD' value may or may not be prime. I need a generalized formula/method. Similar type question was asked before but there was solution…
0
votes
1 answer

Cryptography/modulus equations help

$y \equiv 7x\pmod{26}$ to encrypt the plaintext message “WATCH OUT”. $A=0$ $Z=25$ I would assume that I would need to solve the $y\equiv 7x \pmod{26}$ equation firstly, before I would then be able to encrypt the "watch out" material. At present, I…
0
votes
1 answer

Inverse of a equation with modulo operator

I have this equation: $y=ax+b \quad \pmod{26}$ where a, b are two parameters. I would like to calculate the inverse of this equation, but I don't know which algebra rules I have to apply. Can you help me?
Jhdoe
  • 215
0
votes
1 answer

Determine the remainder when $7^{7^{2019}}$ is divided by 47.

Determine the remainder when $7^{7^{2019}}$ is divided by 47. 47 is prime, perhaps we can do something with that? I'm not sure how to approach this question, any and all help is appreciated. Thanks!
Sania
  • 103