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 $b-a$.

learn more… | top users | synonyms

0
votes
1answer
8 views

Question about congruence modulo notation

I am a bit confused about the semantics (or maybe it would be better to call it semiotics) of the congruence modulo. When we are presented with an expression of the form $$ a \equiv b\ (\textrm{mod}\ ...
3
votes
2answers
19 views

Solving an integer equation

Is it true that if: $x$, $y$, $z$ and $t$ are integers such that: $xz + 7yt = 0$ $and$ $yz + xt = 0$, then $x = y = 0$ $or$ $z = t = 0$? Why or why not? Unless I have miscalculations somewhere ...
2
votes
1answer
33 views

Number Theory: Let $m = 2^ap_1^{b_1}p_2^{b_2}…p_r^{b_r}$ where $a\geq 0,r \geq 0, b_i \geq 1$.

I need to find how many incongruent solutions exist to the equation: $x^2 \equiv 1(mod\space m)$. I'm thinking I need to take a case by case approach, for example when $a = 0$, but these number ...
0
votes
1answer
22 views

Finding the Modular Multiplicative Inverse of a large number

I am practicing some modular arithmetic and I am trying to find the multiplicative inverse of a large number. Here is the problem: 345^-1 mod 76408 I'm not sure how to go about solving this problem. ...
4
votes
5answers
726 views

Modular Inverses

I'm doing a question that states to find the inverse of $19 \pmod {141}$. So far this is what I have: Since $\gcd(19,141) = 1$, an inverse exists to we can use the Euclidean algorithm to solve for ...
-2
votes
1answer
26 views

inversing using Euclid's algorithm

The question is: Find the inverse of 14 mod 37. I don't know how to do, so could someone please explain it? Thanks in advance.
4
votes
1answer
23 views

Find $f_{1}, f_{2}$ in $\mathbb{Z_{6}}[x]$ such that deg$(f_{1})$ = deg$(f_{2}) = 2$ and deg$(f_{1}+f_{2})=1$

Find $f_{1}, f_{2}$ in $\mathbb{Z_{6}}[x]$ such that deg$(f_{1})$ = deg$(f_{2}) = 2$ and deg$(f_{1}+f_{2})=1$ Find $g_{1}, g_{2}$ in $\mathbb{Z_{6}}[x]$ such that deg$(g_{1})$ = deg$(g_{2}) = 1$ and ...
3
votes
2answers
41 views

Polynomial ring addition in $\mathbb{Z_{6}}$

I know this is a very simplest question ever. But, I need help with understanding it. So here it goes... Let, $f(x) = \bar{1}+\bar{2}x+\bar{3}x^2$ and $g(x) = \bar{4}+\bar{5}x$ $\in \mathbb{Z_{6}}.$ ...
1
vote
0answers
21 views

Find a non zero element $z\in \mathbb Z_{100}$ such that $yz = 0_{R}$ and $zy = 0_{R}$ where $y =\overline{ 14}$

Find a non zero element $z\in \mathbb Z_{100}$ such that $yz = 0_{R}$ and $zy = 0_{R}$ where $y =\overline{ 14}$ For this I have found such an element to be $\overline{50}$ since ...
1
vote
1answer
13 views

$a$ has a square root modulo $p$ if and only if its discrete logarithm log$_{g}(a)$ modulo $p - 1$ is even

Questions: Let $p$ be an odd prime and let $g$ be a primitive root modulo $p$. Prove that $a$ has a square root modulo $p$ if and only if its discrete logarithm log$_{g}(a)$ modulo $p - 1$ is even. ...
1
vote
4answers
51 views

$(a+b)^p \equiv a^p + b^p (\mod p)$. Proof. [on hold]

Let $p$ be prime, $a,b \in \mathbb{Z}$. Prove that: $$(a+b)^p \equiv a^p + b^p (\mod p)$$ How to deal with it.
0
votes
1answer
18 views

Finding a module for the series $2^{i}$ from 0 to 219

How can I compute this: $\{ \sum 2^{i}$ for $i \in [0, 219] \} \pmod{13}$ I tried to manipulate the series by using the root principle to find the number of elements divisible by every prime $\leq ...
2
votes
1answer
95 views

How does this periodic trig function that calculates modulus work?

$$ \arctan(\tan(( \mathrm{dividend} - \frac{\mathrm{divisor}}{2}) \times \frac{\pi}{\mathrm{divisor}}))*\frac{\mathrm{divisor}}{\pi}+\frac{\mathrm{divisor}}{2}= \mathrm{dividend} \bmod ...
1
vote
1answer
22 views

Finding all the solutions of a linear equations

I am trying to find all the solutions to the following equation: $5x \equiv 15\pmod{25}$ Here is what I've done: Find the $\mathrm{gcd}(5,25) = 5$; there will be $5$ solutions. Divide the original ...
2
votes
0answers
45 views

eliminate very kth element in mod n… save a given element for last

We are given $1,\ldots,n$ numbers. Let's say we are to save a given number element $k$ for last in elimination. We start eliminating them in the following manner. I eliminate $1$ at first. Then ...
0
votes
2answers
86 views

Why is it safe to assume $M$ is less than all $N$s in Håstad's Broadcast Attack

I am reading the Wikipedia article on Broadcast attack. In the proof, the editor made an assumption that $M$ is less than all $N$. Why is this assumption safe?
0
votes
1answer
42 views

If $2^{k} + 1$ is prime, prove that $k$ has no other prime divisors than $2$. [duplicate]

I am trying to prove this by contradiction: Assume $2^{k} + 1$ is prime. By definition of odd number $2^{k} + 1$ is odd because $2^{k} + 1 = 2\cdot 2^{k-1} + 1$ Then $2^{k} + 1 \pmod{2} \equiv 1 ...
0
votes
2answers
100 views

In Wilson's Theorem Why can we always split integers into mutually inverse pairs?

I mean for example $p=13$ $1*12\equiv-1 \pmod{13}$ then inverse pairs $2*7\equiv1\pmod{13}$ $3*9\equiv1\pmod{13}$ $4*10\equiv1\pmod{13}$ $5*8\equiv1\pmod{13}$ $6*11\equiv1\pmod{13}$
1
vote
1answer
27 views

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.. I am totally lost; at first I thought this could be done by induction, but unfortunately this is not possible (at least I ...
-2
votes
1answer
89 views

Prove $x^{p^2-1}\equiv1\pmod{p^2}$ has exactly $p-1$ solutions for prime $p$ [on hold]

Let $m=p^2$ where $p$ is a prime number. Show that the congruence $x^{m-1}\equiv 1\pmod{m}$ has precisely $p-1$ solutions. Let $m = pq$ where $p$ and $q$ are distinct prime numbers. Show that then ...
2
votes
1answer
52 views

Existence of solution to Congruence relation $(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$

I'm taking the final exam in "Number Theory" tomorrow and stuck with: Prove that $\,\,\forall p\in\mathbb{Z}_p\,$ the congruence relation: $$(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$$ has a ...
1
vote
1answer
34 views

Discrete Logarithm Problem

Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a ...
3
votes
4answers
83 views

How do I prove that if $p$ is prime then $p$ divides $2^{p}-2$?

I know that if $p$ divides $2^{p}-2$ can be written as $2^p - 2 \equiv 0 \bmod p$, but then I get stuck. Im not sure how to take an approach on this.
0
votes
4answers
96 views

Formula for Modulo

What is the formula for modulo (finding the remainder of a division). In programming, the symbol used is generally %. 2%2 = 0 3%2 = 1 5%3 = 2 7%4 = 3 Edit: I ...
-2
votes
2answers
47 views

What is $\sqrt{3}\pmod 2$?

Please explain your answer, thanks. My attempt: It is $\pm 1$ because $(\pm 1)^2\equiv 1\equiv 3\pmod 2$, so $\pm 1\equiv \sqrt{3}$ by taking square roots.
0
votes
2answers
48 views

How to find $\sqrt{3}\pmod 5$?

I was thinking about this but I couldn't solve it. I am trying to find $\sqrt{3}\pmod {10}$. I found that $\sqrt{3}\equiv \pm 1\pmod 2$ but I can't solve $\sqrt{3}\pmod 5$. Thanks
0
votes
2answers
53 views

Show that there exists no integer $x$ such that $3x$ is congruent to 5 (modulo 6)

So far my approach was to rewrite the congruency to $5-3x=6t$ for some integer $t$. My problem is I get stuck in trying to show how $5-3x$ is never divisible by $6$.
1
vote
0answers
25 views

Modular Arithmetic - pairs of additive inverse pairs and multiplicative inverse pairs

I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and ...
2
votes
4answers
70 views

Proving that $x^5 = x \pmod{10}$ for every integer $x$. [duplicate]

Show that $x^5 = x \pmod{10}$ for every integer $x$. How can I approach this? Should I use induction? I am stuck trying to get it in terms of $x+1$. Some feedback would be appreciated.
0
votes
2answers
52 views

General method to solve a modular system

I noticed that if we got a system of modular equations that all equals to $0$ we can always solve the system; for example in a system like this: $$\begin{cases}n \mod m =0 \\n \mod m' =0 \\n \mod m'' ...
1
vote
1answer
34 views

The order of its elements in the additive group $\mathbb{Z}/9\mathbb{Z}$.

I want to determine the order of each element in the additive group $\mathbb{Z}/9\mathbb{Z}=\lbrace \bar{0},\bar{1},\bar{2},\dots, \bar{8}\rbrace$. It is taken from the Example (4) page 20 in Abstract ...
1
vote
1answer
26 views

If $x$ is a square modulo two primes, then it is a square modulo their product

$a, b$ be integers, $p, q$ primes. If $x \equiv a^2 $ (mod $p$) and $x \equiv b^2$ (mod $q$), then $x \equiv c^2$ (mod $pq$) for some interger $c$. I attempted to use Chinese Remainer Theorem, ...
19
votes
5answers
36k views

How to find the inverse modulo m?

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the modular inverse of $7$ with respect to $31$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have ...
1
vote
2answers
46 views

Linear congruences $2X\equiv9\pmod{26},\pmod{25}$

May double that of a natural number let rest $9$ when divided by $26$? And when divided by $25$? I tried: $$2X\equiv9\pmod{26}$$ As $(26,2)=2$ and $2\nmid9$ then the congruence linear not ...
3
votes
4answers
944 views

Not understanding Simple Modulus Congruency

Hi this is my first time posting on here... so please bear with me :P I was just wondering how I can solve something like this: $$25x ≡ 3 \pmod{109}.$$ If someone can give a break down on how to do ...
1
vote
2answers
73 views

using Gauss' algorithm (for linear congruences) for A > B

To solve $Bx \equiv A \pmod{m}$, use Gauss' algorithm. The algorithm works perfectly when $A < B$. For example, to solve $6x \equiv 5 \pmod{11}$: $$x \equiv \frac{5}{6} \equiv \frac{5(2)}{6(2)} ...
1
vote
4answers
953 views

Is it possible to do modulo of a fraction

I am trying to figure out how to take the modulo of a fraction. For example: 1/2 mod 3. When I type it in google calculator I get 1/2. Can anyone explain to me how to do the calculation?
3
votes
4answers
596 views

how do I calculate inverse modulo of a number when the modulus is not prime?

I came through Fermat's Little theorem, and it provides a way to calculate inverse modulo of a number when modulus is a prime. but how do I calculate something like this 37inverse mod 900?
0
votes
1answer
56 views

Solve $9x^8\equiv 8\pmod{17}$

$$9x^8\equiv 8\pmod{17}$$ Is there a way to solve this with out testing all integers $x$ between $1$ and $17$ ?
3
votes
1answer
37 views

How to apply modular division correctly? [duplicate]

As described on Wikipedia: $$\frac{a}{b} \bmod{n} = \left((a \bmod{n})(b^{-1} \bmod n)\right) \bmod n$$ When I apply this formula to the case $(1023/3) \bmod 7$: $$\begin{align*} (1023/3) \bmod ...
0
votes
3answers
63 views

Equation system modulo prime

I have an excercise, it is to solve $$9\equiv_{p}8k_1+k_2$$ $$32\equiv_{p}6k_1+k_2$$ $$45\equiv_{p}11k_1+k_2.$$ $k_2$ is easily eliminated from the equations but I don't know how to proceed from ...
1
vote
3answers
36 views

Euler's theorem (modular arithmetic) for non-coprime integers

I am trying to calculate $10^{130} \bmod 48$ but I need to use Euler's theorem in the process. I noticed that 48 and 10 are not coprime so I couldn't directly apply Euler's theorem. I tried breaking ...
1
vote
1answer
10 views

Primitive roots and 'equivalent exponents'.

If M is a primitive root mod p and M = $\ N^T$ mod p , then the order of N mod p is also (p-1) is this true?
0
votes
1answer
362 views

What will be the multiplicative inverse of square root of 5 with respect to a natural number $M$?

Can such a number $N$ be found such that $\sqrt{5}N \equiv 1 \mod M$? If no,what can be the best approximation for $N$?
0
votes
1answer
38 views

How does the Euler Totient Function apply here?

How many positive integers $< 2013$ are divisible by $2$ Can I somehow use Euler's Totient function to find this?
0
votes
2answers
24 views

Congruence with additional conditions. [closed]

Let $$\left(ac \equiv bc \pmod m\right) \wedge \left(gcd(c,m) = d\right) \implies a \equiv b \pmod {\frac{m}{d}} $$ Is it true? Why? Thanks in advance.
2
votes
1answer
58 views

REVISTED$^1$ - Order: Modular Arithmetic

Relevant Literature: Question: Observe that $2^{10}=1024≡−1 \pmod{25}$.Find the order of $2$ modulo $25$. Thoughts: Direct answers are OK, but I'd like to know if I'm right that what I'm really ...
3
votes
1answer
97 views

$\mathbb{Z}/m\mathbb{Z}$: A Complete Set of Representatives

So, I'm letting ${\scr{A}}=\{a_1,\dots,a_n\}$ be a complete set of representatives (C.S.R.) for $\mathbb{Z}/m\mathbb{Z}$. I'm considering all $b\in \mathbb{Z}$ and seeing if ${\scr{B}}=\{a_1+b, a_2+b, ...
-1
votes
5answers
105 views

$(a,m) = (b,m) = 1 \overset{?}{\implies} (ab,m) = 1$

In words, is this saying that since $a$ shares no common prime factors with $m$ and $b$ shares no common prime factors with $m$ too, then of course the product of $a$ and $b$ wouldn't either!?
1
vote
4answers
69 views

$[4]_{17}[x]_{17} = [2]_{17}$: How to optimally solve this equality.

This notation is found in Concrete Introduction to Higher Algebra. Here is my method: For something like $[3]_{11}[x]_{11}^2=[4]_{11}$ I've just been using C++ code like this: ...