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
2 answers

Computing a large modular power

How do you compute 4948^41 (mod 5963)? I tried to reduce the exponent to 32+8+1. However, I get stuck with the calculations and end up getting numbers that cannot fit in the calculator. Please help.
Ellen
  • 3
0
votes
1 answer

Modular arithmetic and powers

Suppose: $$a=(5^4 \pmod 7)^3 \pmod {13}$$ How would you go about solving this? The only thing I came up with is an ugly polynomial: $a=13k+7l^3+5^{12}$ but this doesn't tell me much. Any starting point would be great.
Dimitri
  • 1,287
0
votes
2 answers

How can I prove that this equality is impossible?

I need to prove that: $$(6 + x^2) \mod 7 = 4$$ is not possible for $x\in \mathbb{N}$. I know the proof would be by contradiction (i.e. assume we have a value of $x$ that solves this equation and reach a contradiction), but I'm not sure here to go…
0
votes
3 answers

Solving system of linear congruences

I have the following: $$12x+28y=20$$ I'm trying to find solutions to the equation above defined by: $12x\equiv 20\pmod {28}$ The GCD is $d = gcd(28,12)=4$ and since $4 | 20 $, then there are 4 solutions that exist. (please correct me if I'm…
Dimitri
  • 1,287
0
votes
2 answers

Finding remainders of numbers with high powers

What is the reminder when $3^{2015}+11^{2014}$ is divided by $61$? All I can observe in this question is that $3^5=(61*4)-1$ and $11^2=(61*2)-1$. Unable to proceed hereafter. Is there a general method to solve such types of modulus operations?
Tejas
  • 2,082
0
votes
1 answer

How many solutions exist to $x^2\equiv 0\pmod k$?

Given two upperbounds $K$ and $X$, and some positive integer $k : 1 \le k \le K$, is there a way to determine for how many values of $x: 1\le x \le X)$ that $x^2\equiv 0\pmod k$?
0
votes
1 answer

Solving for an unknown modulus

I have the following: $$ab \pmod x = 1.$$ $a$ and $b$ are known. Is there an efficient procedure to find the largest possible value of $x$? Edit: What if $a$ and $b$ are too large to factor efficiently though?
Matt
  • 1
  • 2
0
votes
3 answers

Calculate a number (mod)

Calculate: $3^{1234} $ (mod 17) We're not suppose to use any "tricks" like the little theorem or anything else alike because we haven't learned that yet just the the definition of modulo. I tried to do this but it doesn't really…
GinKin
  • 4,429
0
votes
1 answer

Prime divisors of the integer $n^2+n-1$ (using the Legendre symbol)

What made me have a question is the following problem. The prime divisors $p\not=5$ of the integer $n^2+n-1$ are of the form $10k+1$ or $10k+9$. I thought $\left(\frac 5 p\right) = 1$, because $5 \equiv 1 \pmod 4$. So $\left(\frac 5 p\right) =…
jakeoung
  • 1,261
0
votes
0 answers

Smallest possible value of $a$

How do you find the smallest value of $a$ where: $b^a \equiv 1 \pmod{p}$ $b$ is not divisible by $p$, and $p$ is a prime number. Fermat's little theorem works, but it doesn't ensure that $a$ is minimised. What else could be used?
green
  • 21
0
votes
1 answer

Simple Modular Arithmetic

We know that, for example, $2x \equiv 3 \mod 4$ has no solutions since $2\mid 2x, 2\mid 4,$ however 2 does not divide 3. So my question is, how does one get from $2x \equiv 3 \mod 5$ to $x \equiv 4 \mod 5$? In other words, could someone please…
user2342435
  • 133
  • 2
0
votes
2 answers

Congruence Equation x/20 = 7 ( mod 5)

please tell me how to solve this equation : x/20 = 7 ( mod 5 ) I tried too many methods but it does not work.
reem
  • 3
0
votes
1 answer

Finding modular inverse of $q$ modulo $p$, where $q,r$ are prime numbers

I have to write a small program with the following instructions: Given are p and q with p and q different prime numbers. Write a small program that calulates the following values: 1) Determine a solution z for qz ≡ 1 mod p ... My question is: As p…
Munis
  • 1
0
votes
1 answer

modular arithmetic with exponents

I'm looking at the solution manual of a book and it lists a solution for $$[19^3\mod {23}]^2 \pmod {31} \equiv [(-4)^3\mod {23}]^2 \pmod {31} \equiv [-64\mod {23}]^2 \pmod {31}\equiv 5^2 \pmod{31} = 25$$ How does it get from $[19^3\mod {23}]^2 \pmod…
0
votes
1 answer

Computing large exponential modular

My homework question asks me to compute $2^{1386}\mod1387$ without factoring or directly determining whethere 1387 is prime or not; and only use paper, pencil and a basic calculator I used fast exponential method and was able to determine…