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
3answers
50 views

How to solve $100^{63}$ mod 63

I am trying to solve this question but not able to figure out how to approach it. $100^{63} \mod\ {63}$ Please help.
1
vote
1answer
15 views

Simple Modular Arithematic with Negative Numbers

If given an equation in the form: 3 = x mod 13 I know that I can generate a solution set by doing: X = 13q + 3 And ...
1
vote
1answer
24 views

Quadratic modulus

What is a fast way of finding a solution M to a quadratic modulus of the form a == M (M + b) mod n where a and n are very large, and b << a n is the ...
0
votes
0answers
48 views

Showing that 2^(N-1) is equivalent to 1 mod N

My math professor gave us the following problem on a past exam and I didn't get it right then and I still don't know how do it: ...
1
vote
1answer
36 views

Equation $x^2 + y^2 + 1 = 0$ (mod $p$)

How to prove that equation $x^2 + y^2 + 1 = 0$ (mod $p$) has roots? Hints are acceptable.
0
votes
1answer
32 views

Two questions concerning divisibility

I was looking at some proof questions and had difficulty answering a few of them How do I prove these statements below: 1) $3 \mid (10^{n+1} + 10^n + 1)$ 2) $(a-b) \mid (a^n - b^n)$
1
vote
1answer
52 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
21 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
16 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
1answer
20 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
22 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
27 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
28 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
36 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
41 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
12 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
23 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
42 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
28 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
61 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
22 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
31 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
28 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
31 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
28 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
26 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
29 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
38 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
21 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
62 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
44 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
10 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 ...
1
vote
1answer
45 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
29 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
17 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
17 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
250 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
49 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
18 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
20 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
35 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
25 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
83 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
28 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
19 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 ...