Tagged Questions

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
18 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
16 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
17 views

Solving a quadratic congruence (mod p).

Solve x^2 == 6 (mod97). There is an algorithm in my book. Initialization: I1: Determine the integers k,m such that p-1= m2^k, where k>= 1 and m is odd. Then 97 - 1 = 3*2^5, so k = 5 and m = 3. ...
0
votes
2answers
22 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
35 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
29 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
11 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
20 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
34 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 ...
0
votes
1answer
23 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
58 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
21 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
26 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
27 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
30 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
23 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
0answers
15 views

RSA cipher encryption/decryption

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
28 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 ...
0
votes
2answers
31 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
19 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 ...
0
votes
1answer
53 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
43 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
0answers
22 views

Image of a square modulo

Given the following: $b = a^2\ (\text{mod}\ p)$, $p$ is a prime number I want to find way to retrieve $a$ from $b$, how can I do?
1
vote
1answer
9 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 ...
0
votes
0answers
12 views

modular arithmatic query

can anyone explain to me why i am having toruble with the expression: a1/ a2 = a1 * a2 (to the power of -1); a2 (to the power of -1) is an inverse of s2. When I tried to check my understaning of ...
0
votes
1answer
41 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
18 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
0answers
28 views

Equations in modular arithmetic

I'm currently attending a pure mathematics course, the current chapter is on modular arithmetric and solving linear equations in modular arithmetric. That is, equations of the form $a \times_n x = c$. ...
0
votes
1answer
28 views

Integer solution for x * 174582 + y * 1818342 = 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
16 views

Zero divisors and inverstible 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
16 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
240 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
40 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 ...
0
votes
2answers
41 views

how to do Diffie-Hellman-Merkle Key Exchange [closed]

You want to use the Diffie-Hellman-Merkle Key Exchange with $n=93, M=12$ and $a=20$. Find $\alpha$. $$\alpha= M^a \pmod n = 12^{20} \pmod{93}$$ how can I simplify the exponent to a smaller number? so ...
1
vote
1answer
17 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
26 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
19 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
34 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
22 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
76 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
27 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
0answers
9 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
45 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
40 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
19 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 ...
3
votes
5answers
80 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
29 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
21 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 ...
1
vote
0answers
22 views

Proof modular equality by induction

I'm trying to prove using induction that $5^{2^{x-2}} = 1 + 2^x (\mod(2^{x+1}))$ So far, I have: Base case: $x = 2, 5 = 5 (\mod 8)$, It is true. $x = 3, 25 = 9 (\mod 16)$, It is true. Inductive ...
1
vote
2answers
23 views

Stuck with modular arithmetic problem using multiplication property

I have the following problem: Given $k\geq 1$, find $h$ such that $$2^h \frac{4^k-1}{3}-1 \equiv 0 ~(\text{mod}~3).$$ This is my attempt using the invariance of multiplication: $$2^h ...