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

For what values of b does the following system of modular equations have a solution?

$$x \equiv b (100)$$ $$x \equiv b^2 (35)$$ $$x \equiv 3b - 2 (49)$$ If I was pressed for an answer I would say this system was unsolvable. If $x \equiv b(100)$ the $x = b + 100t$. Then $b + 100t \equiv b^2 (35)$ which would imply that $100t \equiv…
0
votes
2 answers

Let $p$ be an odd prime. Prove that if $a\equiv b\pmod{p}$, then $a^p\equiv b^p\pmod{p^2}$

Let $p$ be an odd prime. Prove that if $a\equiv b\pmod{p}$, then $a^p\equiv b^p\pmod{p^2}$ I know how to prove this if we are given $a^p$ is congruent to $a$ mod p, but not when we start with this.
H5159
  • 969
0
votes
1 answer

Quick Modular Property Help

Is this property always true? if $x \mod y = z$, then $ax \mod ay = az$? for all intergers $x,y,z,a$.
Dane Bouchie
  • 1,282
0
votes
1 answer

Modular Arithmetic

I am doing some exam preparation and can't figure out how to do the following question. It seems to be a regular question and was wondering if anyone who could tell me an approach to this style of question in laymen's term as everything tutorial i…
0
votes
2 answers

If $c \not\equiv 0 \pmod p$ then $\forall a \not\equiv 0\ \exists b \not\equiv 1$ so $c+a\equiv ab \pmod p$

Im looking for a correct argumentation of why the folowing holds, any help would be great: For $p$ prime, if $c \not\equiv 0 \pmod p$ then $\forall a \not\equiv 0 \pmod p ~\exists b \not\equiv 1 \pmod p$ such that $c+a\equiv ab \pmod p$ I…
NumberFour
  • 1,157
0
votes
1 answer

How to apply modular arithmatic in expression containing divisions?

How do I find the modulo if the expression contains divisions. Like: $$\frac{p^a-1}{p-1} \pmod{1000,000,007},$$ where $(p^a-1)$ is divisible by $p-1$ and p is a prime, but a may not be. How do I calculate the modulo ?
0
votes
3 answers

Computing elliptic curve finite field modular arithmetic

Sorry for asking such a n00b question but what does the following compute to? $s=(3(16)^2+9)\cdot(2\cdot 5)^{-1}\bmod{23} = 11$ In an online response here, I saw this computes to $11$ but whenever I do the computation I get $8.7$. Can someone show…
0
votes
2 answers

How to prove this modular problem?

Prove that if $n^2+m$ and $n^2-m$ are perfect squares, them $m$ is divisible by $24.$ How to solving this problem?
K.C.S.
  • 183
0
votes
4 answers

Are $a$ and $n$ relatively prime?

Suppose that $a$ and $n$ are integers, $n>1$. Prove that the equation $ax\equiv1(\mod n)$ has a solution if and only if $a$ and $n$ are relatively prime. How to solving this problem?
K.C.S.
  • 183
0
votes
1 answer

Is there this integers

Given an integer n, show that an integer can always be found which contains only the digits 0 and 1 (in the base 10 notation) and which is divisible by n. How to solving this problem?
K.C.S.
  • 183
0
votes
1 answer

How to decide whether a number is inside of wrapped (modular) interval

I am having a problem a finding a suitable formula for deciding whether a number falls inside of modular interval. Example: Let's use $mod$ $100$ and the interval $\langle 90, 10\rangle$. How would you compute if the number $95$ or $0$ falls into…
0
votes
2 answers

Solving modular arithmetic equation.

Need help! I'm having some problem with understanding this equation! We have a similiar example in the book, but I dont really get what they mean. So here is the question. Given 3u = 1 (mod 5), find u? I mean, as far as I understand, 3 = 3 (mod 5),…
0
votes
2 answers

Finding unknown in modulo operation

I have this question on a test 1) find d=gcd(77,50) using euclidean alg. 2)find s and t such that 77s+50t=d 3) use these results to find x such that 50x=4(mod77) Note:the qual sign should have 3 lines For the first part i found d=1 no problem…
0
votes
1 answer

Rules on surjective and Injective

So I am trying to prove $f([a]+[b]) = f([a]) + f([b])$ for $\mathbb Z$ mod $12$ and the same for multiplication... Can you show that this is true based on a function being surjection and injective and any combination of the two without showing…
D-Man
  • 593
0
votes
1 answer

Getting higher powers in modular arithmetic

How would I solve $7^{\ 345}+4^{2313} \equiv x \pmod 3$ ?
user96137