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

Which property of modular arithmetic is being used here?

I came across this example in a video lecture on modular arithmetic. I need to calculate (99^99) modulo 100. It says that since modulo is preserved under multiplication we can just replace 99 in the base by a congruent number that is -1. AFAIK, this…
Devesh Lohumi
  • 195
  • 1
  • 10
0
votes
0 answers

Non integer solutions to mod

I have the question: Solve simultaneously the three congruences 3x≡4(mod 7), 4x≡5(mod 8) and 5x≡6(mod 9). I have found solutions to the first one and last one, which are x≡6(mod 7) and x≡3(mod 9). However, the middle one is giving me some trouble as…
0
votes
1 answer

Given mod3, mod5 and mod7 of a number `x`, how to find the number?

My Problem: x mod(3) = 2 x mod(5) = 4 x mod(7) = 1 Solve for x I was given a formula x = (x mod(3) * 70 + x mod(5) * 21 + x mod(7) * 15) mod(105) to solve for x. I want to know how to derive this formula. I can see a relation between the numbers…
One Face
  • 101
0
votes
1 answer

Let $x$ and $y$ be integers such that $x ≡ 3$ (mod $9$) and y ≡$ 4$ (mod $9$). Is it possible that $ 20x + 3y^3 ≡ 6$ (mod $9$)

I have problem answering this question. I know the answer is not possible but I by simply substitute the 3 and 4 but I have clue why so. Can anyone give me an explanation or a correct way to answer this question properly. Any help is appreciated.…
Qi Yuan
  • 11
0
votes
1 answer

Modulus arithmetic / multiplicative order question

I'm working on a problem about shuffling decks, using https://mathworld.wolfram.com/Out-Shuffle.html So I need to find all deck sizes $n$ where you can shuffle (using out-shuffle) so that it returns to the original order in a given number $k$…
gunnar2k
  • 3
  • 4
0
votes
0 answers

Find $a$ in $a^2 \equiv 1 \pmod b$ given $b$ where $a < b-1$

Given the equivalence $a^2 \equiv 1 \pmod b$ (where $b$ is known) is there an efficient way to determine if an answer other than $a = 1$ exists? Is there an efficient way to find the answer(s), especially the greatest possible value of $a$? The only…
0
votes
1 answer

prove $x = (b-a) \mod m$

If $(ai+x)\mod m = b $ then how can we prove that $x = (b-a)\mod m$? If it is not correct then what is correct value for $x$?
0
votes
1 answer

How to calculate $1900^{13} \pmod{2537}$

How to calculate $1900^{13} \pmod{2537}$ I should be able to do this problem but I don't figure a fast way of calculating it. Edit: I find reduced the problem to solve: $X≡12^{13}$mod$59$ and $X≡2^{39}$mod$43$ and I don't know how to…
iggykimi
  • 349
0
votes
1 answer

balls in boxes counting problem

Mady has an infinite number of balls and empty boxes available to her. The empty boxes, each capable of holding four balls, are arranged in a row from left to right. At the first step, she places a ball in the first box of the row. At each…
0
votes
1 answer

Prove that if m is a square integer then m is neither congruent to 2 modulo 5 nor congruent to 3 modulo 5

Prove that if m is a square integer then m is neither congruent to 2 modulo 5 nor congruent to 3 modulo 5. I've seen this problem done for modulo 4 and modulo 8 but this doesn't seem to work for me as the 2k doesn't square nicely to a 4. Maybe I'm…
0
votes
3 answers

For $7(a+b)^2 = 320m$. Find The Value Of $a$ And $b$.

suppose that $a$ and $b$ are natural numbers, $a ≠ 0$ and $b ≠ 0$, and $lcm(a,b) = m$. Given that $$7(a+b)^2 = 320m$$ Find the possible values for both $a$ and $b$.
0
votes
3 answers

$a^{\phi(p)} \equiv 1 \pmod{p}$ if $a$ and $p$ are relatively prime.

Why is it if we use 1 2 3 4 mod 5 and we take x^3 of these numbers, we come to: 1 3 2 4 (all numbers are different as you can see)? Why are they all different. Thanks Explanation: $a^{\phi(p)} \equiv 1 \pmod{p}$ if $a$ and $p$ are relatively prime.…
0
votes
1 answer

Find smallest $x, y$

Find smallest natural numbers $x,y$ such that $$ 49x = 125y.$$ Will this require some special modular arithmetic property or am I missing something?
user737542
0
votes
1 answer

Find the least residue

for $125$ mod $13$ and $-43$ mod $7$ $13$ goes into $125$ $9$ times with a remainder of $8$ $7$ goes into $-43$ $6$ times with a remainder of $1$ So the least residues are $8$ and $1$(possibly $-1$)? Is it really that easy?
K. Gibson
  • 2,381
0
votes
6 answers

Modulo operation: Why does -1 = 59 (mod 60), whereas 1 = 1(mod 60)?

The latter makes perfect sense to me, but what's the skinny with the former? I researched but couldn't understand the drift. TIA
computronium
  • 121
  • 4