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
0answers
10 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
24 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} ...
0
votes
0answers
7 views

one-to-one correspondence with a set of primitive dirichlet charchter

Let $$\operatorname{Prim}_{N}=\{\xi \mid \xi \text{ a primitive Dirichlet charchter mod } F \text{ with } F\mid N\}$$ and $$\operatorname{Char}_{N}=\{\xi" \mid \xi" \text{ Dirichlet charchter mod } N ...
1
vote
2answers
17 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
27 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
229 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
34 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
40 views

how to do Diffie-Hellman-Merkle Key Exchange [on hold]

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
15 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
33 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
21 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 ...
2
votes
0answers
28 views

A primitive root exists modulo $n$ if and only if $n=2$, $n=4$, $n=p^k$, or $n=2p^k$ with $p$ an odd prime.

I have already proven that primitive roots exist modulo $p^k$ and $2p^k$ for an odd prime $p$. I'm having trouble proving the other direction. Is it simply due to the fact that if $p,q$ are distinct ...
0
votes
2answers
26 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
8 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
44 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 ...
-1
votes
0answers
11 views

how to do DHM key exchange [closed]

You want to use the Diffie-Hellman-Merkle Key Exchange with n=93, M=12 and a=20. Find α. What would the answer be? I can't figure out how to do this
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 ...
2
votes
5answers
74 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
18 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
20 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 ...
0
votes
2answers
13 views

If a is not relatively prime to n prove modulo property

If $n>1$ is integer and $1\le a \le n$ is integer such that $(a,n)\neq 1$ then prove there exist integer $1 \le b <n $ such that $ab \equiv 0(mod \; n)$ I have tried everything from going to ...
1
vote
1answer
65 views

Product of roots of unity

Does somebody have a nice proof of the following? $$\prod_{m=1}^{n-1} \frac{e^{2\pi i k m/n} - 1}{e^{2 \pi i m / n} - 1} = \begin{cases} 1 & \text{ if $\gcd(k, n) = 1$} \\ 0 & ...
0
votes
1answer
30 views

If $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$, then $ab \pmod 3 \equiv 2$

I'm stuck on this this problem: Let $a$ and $b$ be positive integers with $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$. Prove that $ab \pmod 3 \equiv 2$. I think the first step for the direct ...
0
votes
0answers
22 views

Modulo and power calculation [closed]

Let $A{^-}{^n}$ mod X = ($A{^-}{^1}$ mod X )${^n}$ mod X for $n>0$ Now we want to compute $A^B$ mod X fro given A,B and X provided A and B are coprime. Note : $A{^−}{^1}$ mod X refers to the ...
1
vote
1answer
29 views

What does the notation $\equiv 1\ (\text{mod}\ p)$ mean?

I'm trying to understand the Fermat theory : $a^{p-1} \equiv 1\ (\text{mod}\ p)$ I know that $a\ (\text{mod}\ p)$ gives the remainder of division of $a$ by $p$. So what is $\equiv 1\ (\text{mod}\ ...
1
vote
2answers
33 views

Modular Inverse

Calculate the Following $ (2^{19808}+6)^{-1} +1$ Mod (11) I'm completely lost here for several reasons. First of all the large power of 2 just throws me off and secondly I've seen inverse equations ...
0
votes
1answer
24 views

Obtain Base in this equation

If we have below equation and know that $6$ and $3$ are answers of this equation obtain base of these equation: $$X^2 - 11X + 22 = 0$$
-1
votes
2answers
30 views

Find the value of X when X is positive intigers. [closed]

I'm doing my brothers homework but he don't know how to do this.Find the answer of the equation below. $$2555^{2012}+2012^{2555}≡x\pmod{11}$$
3
votes
2answers
46 views

How many group homomorphisms are there from Zn to Zm?

In looking up this question, I found this site: Physics Forums. In it, someone claims that $f(x) = kx$ is a homomorphism from the group $\mathbb{Z}_{m}$ to $\mathbb{Z}_{n}$ if $m$ divides $kn$. I ...
0
votes
1answer
29 views

Calculus showing with mods

I got this problem from my Calculus II teacher, I have no idea how to approach it... Show that if $a,b,c$, and $d$ are integers such that $a\equiv b\pmod m$ and $c\equiv d\pmod m$, then $a+c\equiv ...
0
votes
2answers
19 views

Square roots and modular arithmetic

Find 4 different square roots of: I have no idea how to get started on this, could someone explain what the first step would be?! a. 1mod35 b. 1mod77
1
vote
3answers
25 views

How to simplify this alternating modulo expression?

The value of $(1000^i \mod 7)$ alternates between 1 and 6, as such: $$ 1000^0 \mod 7 = 1 $$ $$ 1000^1 \mod 7 = 6 $$ $$ 1000^2 \mod 7 = 1 $$ $$ 1000^3 \mod 7 = 6 $$ But as $i$ grows larger, these ...
0
votes
3answers
20 views

Modular Arithmetic: using congruence to find remainder

How do I use the fact that if $a = b \pmod n$ and $c = d\pmod n$ then $ac = bd\pmod n$ to find the remainder when $3^{11}$ is divided by $7$?
2
votes
1answer
26 views

Equivalence classes modulo 7 are pairwise disjoint

Where do I got from here? I really really have no idea.
2
votes
3answers
27 views

Integer solution to multiple modular arithmetic equations

So i understand how to do this when it is just x, but now with multiples of x I am a little confused, and there's no example in my textbook of this. I just need a push in the right direction for how ...
0
votes
2answers
37 views

modular arithmetic congruence

Simplify the following congruence: $$−169 \equiv \text{ ?} \mod 52 $$ (By simplify, we mean find the smallest non-negative whole number which is congruent to $-169$ modulo $52$.) Simplify the ...
1
vote
2answers
42 views

Modular Arithmetic/Number Theory

(Not really sure about my work, so if you could tell me if I am on the right track that would be great!) Find an integer x so that: a. $x\equiv1\pmod{13}$ and $x\equiv1\pmod{36}$ Using the ...
-2
votes
1answer
27 views

How can i do this algebra question?

The question is show that the relation $a\sim b$ defined by $a\equiv b \bmod 7$ is an equivalence relation on $\mathbb{Z}$. How many equivalence classes are there? Let us call them $[0]$, $[1]$, ..., ...
0
votes
0answers
18 views

Recurrences with modulo

Is there any specific way to solve recurrence of form (example): $$f(x) = (a \cdot f(x-1) + c) \bmod{r} $$ (when recurrence involves modulo). For recurrence without modular arithmetic I could use ...
0
votes
4answers
32 views

Calculating $3/10$ in $\mathbb{Z}_{13}$

I'm trying to calculate $\frac{3}{10}$,working in $\mathbb{Z}_{13}$. Is this the correct approach? Let $x=\frac{3}{10} \iff 10x \equiv 3 \bmod 13 \iff 10x-3=13k \iff 10x=13k+3$ for some $k \in ...
0
votes
2answers
19 views

Rever direction modulo operator?

This: i = ((i + 1) % itemArray.length assigns to i the next space going towards the right in a circular manner. Is there a way ...