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

1
vote
1answer
84 views

How to compute: $(89^{3} \bmod 79)^4\bmod 26$?

How to compute: $(89^{3} \bmod 79)^4\bmod 26$?? It's easy to calculate it by evaluating $89^{3}$ first and then mod $79$, but it seems stupid to do it this way. Do we have a faster way to evaluate ...
0
votes
1answer
26 views

If $a\equiv 4\pmod {13}$, a is integer, Find c ($0 \leq c \leq 12$) so that $c\equiv 9a\pmod {13}$

If $a\equiv 4\pmod {13}$, a is integer, Find c ($0 \leq c \leq 12$) so that $c\equiv 9a\pmod {13}$. I translated these into the form of definition: 13 | a-4 and 13|c-9a, then I got stuck on it. I ...
0
votes
1answer
34 views

Method to solve for a number in modulus equation.

If you had an equation of 12 = (8000 + B) mod 13 You could guess and check a little and arrive at B = 7. My question is what is the best way to solve these? Is there a defined method to get B?
0
votes
2answers
113 views

Does $x^2 + x + 1 \equiv 0 \mod p$ have a solution?

Problem: I am trying to prove that $$ x^2 + x + 1 \equiv 0 \mod p $$ has a solution where $p$ is a prime such that $p \equiv 1 \mod 3$, without using quadratic reciprocity. I am also suspecting that ...
0
votes
1answer
46 views

polynomial modulo polynomial

If $h(x) = x^2 + 1$, $g(x) = x^2 + x + 1$ and $f(x) = x^3 + x + 1$, then $$ \begin{align} g(x)h(x) \mod f(x) &\equiv (x^2 + x + 1)(x^2 +1) \mod x^3 + x + 1 \\ &\equiv x^4 + x^3 + 2x^2 + x + ...
1
vote
1answer
90 views

Secret sharing: modular arithmetic

I have this problem of sharing a secret code $n\in\mathbb{Z}$ such that $0\le n\le250$ among five people. There are 5 people, each one of whom receives a secret number $s_i$, $1\le i\le 5$ such that ...
0
votes
1answer
58 views

Solving a quadratic congruence (mod p).

Solve $x^2 \equiv 6 (mod~97)$. There is an algorithm in my book. Initialization: I1: Determine the integers $k,m$ such that $p-1= m \cdot 2^k$, where $k \geq 1$ and m is odd. Then $97 - 1 = 3 ...
0
votes
2answers
53 views

Combining GCD and congruences

Let $a, b, m, k \in \Bbb Z$ such that $m\ge2$ and $k\not=0$. Let $d=\gcd(k,m)$. Prove that if $a\equiv b\pmod m$ and $k$ is a common divisor of $a$ and $b$, then ${\frac ak}\equiv {\frac bk}\pmod ...
0
votes
1answer
53 views

Proofing the existence of a non-zero congruence class

Let $m\ge2$ be an integer. Show that if there is an integer $a$ such that $\gcd(a,m)=d\not=1$, then there exists a non-zero congruence class $[x]$ in $\mathbb{Z}_m$, such that $[a]\cdot[x]=[0]$. I ...
2
votes
3answers
53 views

Solve $9x$ $\equiv 4 \mod1453$

In Underwood Dudley's Number theory book second edition chapter 5 problem 7 I encountered this problem: Solve $9x\equiv 4 \mod1453$ I know that since $gcd(9,1453)=1$, there exists a unique solution. ...
0
votes
0answers
17 views

Will XORing any data with random data produce a random result?

Provided you have a stream of input data and a stream of random data both in the set (0,1). The random is data truly random, that is, unpredictable by the user and ...
0
votes
2answers
56 views

Rules for Calculating Modulo

I have two questions about using modulation in equations. My first question is what notation is the right to use (i.e. x%y or mod(x, y))? The second is what are its properties for adding, multiplying, ...
0
votes
1answer
109 views

Generator of $Z_p^*$ with large p

I have to find a generator for $Z_{p}^*$. The prime number p is $2425967623052370772757633156976982469681$. My prime factors for (p-1) is according to 1 ...
1
vote
1answer
51 views

Showing that the linear twist map is sensitive dependent

Choose $\Delta=\frac{1}{2}$ (I believe this value should work). let $\delta > 0$ and let $\textbf{x}_1=(x_1,y_1) \in X$. I assuming that $d$ is the Euclidean distance. Somehow I think we ...
1
vote
3answers
78 views

Finding remainders using modulo

Determine the remainder of $2014^{2015} \cdot 2016^{2017} + 2018^{2019}$ divided by 13. I can't figure out how to manipulate the 2018 part to get it to some form of 13. Any suggestions?
1
vote
0answers
29 views

Question about a particular case of the sum of three squares.

I was recently given a math problem by a friend; the challenge was to find a rectangular prism whose side lengths (including diagonals and space diagonal) were all natural numbers. I found that for ...
0
votes
1answer
80 views

Solving a system of modular power congruences

I have to find the $x$ value such that $x^k \equiv a_1 \pmod n$ and $x^q \equiv a_2 \pmod n$, where $k$, $q$, $a_1$, $a_2$ are known constants and $n$ is any number. Is there a method to find $x$ ...
0
votes
3answers
75 views

Multiplicative inverse

What is the multiplicative inverse of 7 modulo 11? Is this correct: $$7 = 11(0) +7$$ $$11 = 7(1) +4$$ $$7 = 4(1) +3$$ $$4 = 3(1) +1$$ We then take 3 equations: $$4 = 11 + 7(-1)$$ $$3 = 7 + 4(-1)$$ ...
0
votes
2answers
48 views

Factorization and modular inverses

In this post in the last method the factorials were factorized. But I don't quite understand how that works. Lets say we have $$ (-24)^{-1}+(6)^{-1} +(-2)^{-1}$$ modulo a prime $p$, for instance ...
3
votes
1answer
79 views

primitive root mod25

Verify that 2 is a primitive root mod 25. I just want to make sure my understanding of what a primitive root is is clear. So to show my work I calculated 2^1mod25 up to 2^24mod25, and showed that ...
0
votes
1answer
59 views

Is $7$ a Quadratic Residue mod 101?

Question: Is $7$ a Quadratic Residue mod 101? Attempt: Theorem 9.1 states that the number $a$ is a Quadratic Residue if and only if $a^{\frac{p-1}{2}} \equiv 1$ (mod $p)$. Suppose ...
0
votes
1answer
49 views

RSA cipher Encryption with $n=210757$ and $a=3$ and Decryption with $n=14659$ and $a=3$

I think I understand correctly how to encrypt something with an RSA cipher, but I am a little lost on how to find the decryption key...(also I apologize for the formatting errors) An RSA cipher is ...
2
votes
2answers
51 views

Use modular arithmetic to show that a number is divisible by 11 iff the sum of its alternating digits is divisible by 11

We can expand the number $n = n_0 + 10n_1 + ... + (10^s)n_s$ Then we have $10^k ≡ (-1)^k \mod11$. How do we go from here to here: $n ≡ n_0 - n_1 + ... + (-1)^s n_s \mod 11$ I do not understand ...
1
vote
1answer
36 views

Showing multiplicative inverse has the same order $\pmod{p}$?

Suppose that $a$ has order $h \pmod{p}$ and $a\overline{a} \equiv 1 \pmod{p}$. Show $\overline{a}$ also has order $h$. I'm a little confused as to how to start proving this -- I know that if $a$ has ...
0
votes
2answers
82 views

Prove that if a $\in \mathbb{Z}$ then $a^{3} \equiv a(mod 3)$

Prove that if a $\in \mathbb{Z}$ then $a^{3} \equiv a(mod 3)$ So, the ways I have learned (or am learning, rather) to do proofs is using direct, contrapositive and contradiction. So, I started it ...
1
vote
1answer
26 views

Find all $x \in\mathbb Z$ such that $16x\equiv 26\pmod{42}$

I got stuck with this seemingly easy problem stated below: Find all $x \in\mathbb Z$ such that $$16x\equiv 26\pmod{42}$$ I tried the following: $$ 16x \equiv 26 \pmod{42}\Longleftrightarrow 42 ...
1
vote
1answer
98 views

Proving congruence class

Let $a$ and $m$ be integers such that $m ≥ 1$. Consider the congruence class of $a$, $[a]$ modulo $m$. It follows that $∀ x ∈ [a], \gcd(x, m) = \gcd(a, m)$. I have my algebra midterm in two ...
1
vote
2answers
79 views

Show that 47 divides 5^{23}+1

Show that $47$ divides $5^{23}+1.$ My attempt: Since 47 is prime and 47 does not divide 5, by Fermat's Little Theorem, $5^{47-1} \equiv 1$ (mod 47) $5^{46} \equiv 1$ (mod 47) Now I noticed that ...
1
vote
1answer
14 views

Does there exist a positive integer $k$ such that $(g_i^k)_{i=1}^{\infty},\ g_i^k=p_{i+k}-p_i$ is non-decreasing for all sufficiently large $i$?

Does there exist a positive integer $k$ such that $(g_i^k)_{i=1}^{\infty},\ g_i^k=p_{i+k}-p_i$ is non-decreasing for all sufficiently large $i$, where $p_i$ is the $ith$ prime? $g_{i+1}^k\geq ...
1
vote
1answer
72 views

Proving property of congruence - help needed

Let $c,d,m,k ∈ \mathbb{Z}$ such that $m ≥ 2$ and $k$ is not zero. Let $f = \gcd(k,m)$. If $c \equiv d \pmod m $ and $k$ divides both $c$ and $d$, then $$ \frac{c}{k} \equiv \frac{d}{k} ...
1
vote
2answers
23 views

Solve for x when x is on both sides of modular equation

This question is purely out of curiosity. My little brother got a question for homework to find a rectangle where the Area = Outline. Both sides must also be integers, obviously. He found the square ...
0
votes
1answer
39 views

Integer solution for $174582x + 1818342y = 54$

How can I find an integer solution for $x$ and $y$ for this problem type? I think I have to find a modulo relation between $54, 174582$ and $1818342$, but I am clueless.
2
votes
1answer
50 views

Zero divisors and invertible elements

I have learned about $X_n = \mathbb{Z} / n\mathbb{Z}$. I understand that a zero divisor is an element $x\neq 0$ in $X_n$ such that $xy = 0$ for some $y\neq 0$. I understand that an element $x$ in ...
0
votes
1answer
81 views

How can I prove that the inverse of $n-1$ in $U(n) = \mathbb{Z}_n^{\times}$ is $n-1$?

Where $U(n)$ is multiplicative group $mod(n)$. It seems obvious but how can I actually prove it? From modular arithmetics we have: $(n-1)a = nk+1$, so $a=(nk+1)/(n-1)$, which should be an integer ...
7
votes
2answers
1k views

Proving a palindromic integer with an even number of digits is divisible by 11

I'm in an introductory course for discrete math so I'm a novice at English proofs. I'm not sure if my reasoning here is valid or if I'm using modular arithmetic correctly. Specifically the line I ...
1
vote
1answer
123 views

attack on RSA (factoring when knowing e and d)

This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this ...
1
vote
1answer
35 views

reducing the modulus of a Dirichlet character

Let $\chi$ be a Dirichlet character modulo $N$. Let $M$ be a positive divisor of $N$ such that $$\text{radical}(N)=\text{radical}(M).$$ Is $\chi$ be a character modulo $M$? Best regards.
0
votes
1answer
43 views

Modular arithmetic - is this a “legal” substitution?

I know that $$a \equiv b ~(\text{mod}~3)$$ and $$c \cdot a \equiv 1 ~(\text{mod}~3)$$ Can I substitute $a$ with $b$? I mean: $$c\cdot b \equiv 1 ~(\text{mod}~3)$$
0
votes
1answer
25 views

Problem with modulo in field

I have problem with comprehending how works number in field when it's rasied to negative power. For instance if we have $4^{-1}$ at $Z_{5}$ I tried to write it as $4\cdot 4^{-1}+4^{-1}=4^{-1}(1+4)$ ...
0
votes
1answer
97 views

Modular Arithmetic Root

Find a cube root of 97mod101 gracefully. I don't really know where to get started...could someone help me? I don't expect you to do the calculations, but could you give me a hint written out in ...
0
votes
2answers
204 views

Correct behaviour of mod operation compared to Google calculator

What is happening here? Why is the first calculation returning an integer, but not the second calculation? What are the rules for computing mod for floats and negative numbers?
2
votes
4answers
103 views

Last 3 digits of $7^{12341}$

I know that I need to reduce $7^{12341} \pmod {1000}$ By Euler I have $7^{\phi(1000)}\equiv 7^{400}\equiv1\pmod{1000}$ That leaves me with the monster $7^{341}\pmod{1000}$ Is there a way to reduce ...
0
votes
2answers
72 views

Find a prime $p$ satisfying $p \equiv 1338 \mod 1115$

Find a prime $p$ satisfying $p \equiv 1338 \mod 1115$. Are there infinitely many such primes. A little confused about this problem, any help or advice?
1
vote
1answer
85 views

how to sum the divisors of N mod K if all I have is N mod K?

The input to this problem is N. I have to calculate 2 things: 1 - N! mod (10^9 + 7) 2 - sum of all divisors of N! mod (10^9 + 7) I know how to do the first step, I'm wondering if there is a way ...
2
votes
2answers
321 views

Solving Simultaneous Equations - Hill Cipher

I have searched but an unable to find any examples like what I am faced with. Plaintext = SOLVED CipherText = GEZXDS 2x2 encryption matrix $$ \left(\begin{matrix} 11 & 21 \\ 4 & 3 ...
5
votes
2answers
54 views

$x^2+1=0$ in $\mathbb{Z}_7$

$x^2+1=0$ in $\mathbb{Z}_7$ By trying each number, I see that there is no solution, is this correct? And could you help me with a more direct solution, since this method is not going to work for ...
2
votes
0answers
50 views

Divisibility in different Modulo.

So I've actually been working with congruences recently in class and most of the time I end up using Fermat or the Euler Totient function to simplify a large exponent. In general, I run into a ...
2
votes
4answers
127 views

How to prove that $8^{18} - 1$ is divisible by $7$ [duplicate]

How to prove that: $$ 8^{18}-1\equiv0\pmod7 $$ In the simplest way?
1
vote
1answer
58 views

Derivative of Diffie Hellman

Looking to get some clarification on this. We have the same three protagonists, Bob and Alice, trying to send each other a message. And Eve trying to figure out the message sent by Bob and Alice. ...
0
votes
1answer
2k views

Polynomial Arithmetic Modulo 2 (CRC Error Correcting Codes)

I'm trying to understand how to calculate CRC (Cyclic Redundancy Codes) of a message using polynomial division modulo 2. The textbook Computer Networks: A Systems Approach gives the following rules ...