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

Find two integers between 1 and 100

Can anyone help me with this? Thank you very much! Problem: Find two integers between 1 and 100 such that for each: a) if you divide by 4, the remainder is 3; b) if you divide by 3, the remainder is 1; and c) if you divide by 5, the remainder is…
learning
  • 1,749
1
vote
4 answers

Find smallest $x$ such that $x=59 \pmod {60}$ and $x=1 \pmod 7$

Is a simple way to solve the problem? The method I used is to list all numbers from equation (1) and then see which one give remainder $1$ when divided by $7$. This doesn't seems a very smart way. Problem: Find smallest $x$ that satisfies $$x=59…
learning
  • 1,749
1
vote
2 answers

Known rules for multiplication of modulo operator

Say for example I have the formula: y = x%2 * x%3 or to put it in word notation: y = mod(x,2) * mod(x,3) Is there any way to combine them to leave only 1 modulo operator e.g. y = mod(x,k) (k will likely have to include an x term, or the x term…
1
vote
1 answer

Modular multiplication by many inverses

I need to multiply a number x by modular inverse of y , and then with modular inverse of z and so many numbers . For example $$F=x\cdot (y)^{-1}\cdot (z)^{-1}\cdot (z_1)^{-1}... $$ Now beacause of this I need to calculate the mod. inverse of each…
1
vote
2 answers

Evaluating the remainder of $652^{679} : 851$

Evaluating the remainder of $652^{679} : 851$ I'm having trouble solving this problem, specially because I saw congruence properties a long time ago, but this is what I tried: $652^{679}={652^{7}}^{97} $, but $652^7$ isn't congruent to $851$. I…
user286485
1
vote
0 answers

Calculate modulo expression

How does one evaluate the expression; $$5\times52^{366} \mod367^1$$ I can infer from the exercise solutions that $52^{366} ≡ 1 \mod 367$, but why?
1
vote
1 answer

Prove that for integers $a$, $b$, and $n$, if $a$ and $b$ are each relatively prime to $n$, then the product $ab$ is also relatively prime to $n$.

Please help! I need a proof using modulars on proving that with integers $a$, $b$, and $n$, if $a$ and $b$ are each relatively prime to $n$ then the product $ab$ is also relatively prime to $n$. So far, what I really need help with is how to express…
1
vote
1 answer

Modular arithmetic with negative numbers

Is this correct -347 mod 6 = -5 Or is this correct -347 mod 6 = +1
the_prole
  • 159
1
vote
3 answers

Modulo with negative numbers

When I input this in wolfram I get false -347 mod 6 = 5 When I input this I get true -347 mod 6 = 1 And yet I know $-5 \equiv 1$ And additionally $-6*57 - 5 = -347$ but $-6*57 - 1 \neq -347$ So it's strange that Wolfram's answer is true…
the_prole
  • 159
1
vote
3 answers

$2^a \pmod{13} \equiv 5$ solve to find a formally

I can seem to find any formal proof that would help me derived a knowing $2^a \pmod{13} = 5$ ? The following is given $2^a \pmod{13} = 5$
John
  • 11
1
vote
3 answers

Modular Algebra in Finding Roots

I'm playing around with this problem. $$x^{2} - 2x + 10 \equiv 7 \ \text{mod} \ 6$$ Find the equivalence class(es) in $\mathbb{Z_{6}}$ solving this. The following doesn't work out: $$x^{2} - 2x + 3 \equiv 0 \ \text{mod} \ 6$$ $$(x-1)(x-2)…
Muno
  • 1,509
1
vote
1 answer

Find the modular arithmatic of mod p mod q.

I have an expression say $$x = ((a \bmod p) \bmod q)$$ Now given $x, p,q$, I need to find out the actual value of $a$. How can I do it? For an example I have: $$p = 109,\quad q = 26,\quad a = 171$$ $$x = (171 \bmod 109) \bmod 26 = 62 \bmod 26 …
1
vote
1 answer

Finding multiples of three given a few simple rules

We were given this problem the other day and it seems a little over my head, so I thought I'd share it here for any possible advice or assistance :). The problem is as follows: Initially, $x = 1$. For each iteration, you may execute one of the…
Flaze
  • 11
1
vote
0 answers

Modulo pattern with zero skipped

Is there a way to find a modular partern in which 0 doesn't exist. For eg : mod(x,6) 012345012345.... I'd like : 1234512345.... I need it for a rotation in a list but I cant use 0 Thanks !
1
vote
2 answers

Finding ALL solutions of the modular arithmetic equation $25x \equiv 10 \pmod{40}$

I am unsure how to solve the following problem. I was able to find similar questions, but had trouble understanding them since they did not show full solutions. The question: Find ALL solutions (between $1$ & $40$) to the equation $25x \equiv 10…
Tomm
  • 11