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

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
23 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
69 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 ...
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
38 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 ...
-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
27 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
23 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
28 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 ...
0
votes
1answer
33 views

$a^n = a$ mod ($n$)

Is the following a valid proof Let $a = g^k$ mod $n$ where $g$ is a primitive root of $n$ $a^n = (g^k)^n \text{mod} (n) = (g^n)^k \text{mod }(n) = g^k \text{mod}(n)$ [as $g^n = g$ mod $n$] $= a$ ...
2
votes
1answer
81 views

Prove that $r(2^{55555})$ divisible by $5^5$

In this question there is a comment by @amclade, that $$r\left(2^{55555}\right) \equiv 0 \pmod{5^5},$$ where $r : \mathbb{N} \rightarrow \mathbb{N}$ function gives the reverse of a number. I've ...
0
votes
2answers
29 views

Find the least positive residue of $5^{16} \bmod 17$

I need some help on finding the least positive residues. Not sure what the correct approach is to take on these types of problems and the book I'm reading isn't helping me. ** UPDATE ** If 17 was ...
1
vote
2answers
59 views

Can this be solve using modular arithmetic? $k$ is prime $\Rightarrow$ $8k+1$ is prime

Is the following statement true or false? $\forall k \in \mathbb{N}, k$ is prime $\Rightarrow$ $8k+1$ is prime The answer is that the statement is false because if $k=7$, then $k$ is prime but ...
0
votes
2answers
32 views

How do I count all values that satisfy X mod N=1 in the range [A,B]

I want to count how many values of x in range [A,B] give remainder of 1 when divided by N. Is there any formula I can apply?
0
votes
1answer
45 views

Calculate$ (n+m-1)C_n \mod 10^9+7$ efficiently

I want to calculate $(n+m-1)C_n \mod 1000000007$. where $n$ can be between $1$ and $10^9$. $m$ will not exceed $30$. How do I calculate it efficiently.
1
vote
0answers
52 views

Find all numbers $x$ satisfying $x^3 \equiv 1 \pmod A$.

Given any two numbers $M,N \in \{1,2,\ldots,10^{18}\}$, find all numbers $x$ lying between $M$ and $N$ satisfying $$x^3\equiv1 \pmod A,$$ where $A$ can be any number. I know the case when A is even. ...
1
vote
1answer
26 views

Find the remainder of $(p-2)!$ module $p$, where $p$ is a prime $\geq 3$

My attempt: From Wilson's Theorem: For a prime $p$, $$(p-1)! \equiv (-1) \pmod p$$ Multiplying both sides by $(p-2)$, $$(p-2)! \equiv -(p-2) \pmod p$$ i.e. $$(p-2)! \equiv 2 \pmod p$$ So the ...
1
vote
5answers
2k views

Prove that the sum of three consecutive squares, minus two is a multiple of 3

Prove that if you add the squares of three consecutive integer numbers and then subtract two, you always get a multiple of 3.
0
votes
7answers
60 views

Show that if a positive integer $ n $ is composite then $ R(n) = \frac{10^{n}-1}{9}= 111…11 (n times) $ is composite [duplicate]

Show that if a positive integer $ n $ is composite then $ R(n) = \frac{10^{n}-1}{9}= \underset{n\text{ times}}{\underbrace{111...11}} $ is composite I attempted a both a normal proof and proof by ...
3
votes
5answers
91 views

How to select the right modulus to prove that there do not exist integers $a$ and $b$ such that $a^2+b^2=1234567$?

I understand the solution but I don't know how the author decided to start with modulo 4 instead of something else? What is it about the expression $a^2+b2=1234567$ that would trigger us to select ...
0
votes
2answers
32 views

Help me understand the proof of $a \equiv b \mod m \Rightarrow r_m(a)=r_m(b)$

Let: $r_m:\mathbb{Z}\rightarrow R_m$ where $r_m(a)=r\Leftrightarrow a \equiv r \mod m $ and $r\in R_m$ where $R_m$ is the set of residues modulo $m$. I understand the above proof until $r' ...
0
votes
0answers
16 views

Congruence and modular arithmetic problem

Suppose that a and b are nonzero integers, p is a prime, and p does not divide ab. Show that the congruence ax ≡ b(mod p) has infinitely many integral solutions? I feel as if 2x≡5(mod7) is a ...
0
votes
1answer
58 views

Number of roots of $x^3 \equiv 1 \pmod p$

How to find the number of roots of $x^3 \equiv 1 \pmod p$ in an interval $[a,b]$? For instance, let $p=31$ and $[a,b] = [1,100]$ so the equation becomes $x^3 \equiv 1 \pmod {31}$
1
vote
1answer
35 views

Fermat's Little theorem to find primes

Find $4$ primes that divide $14^{60} - 33^{60}$ okay, so the easiest thing to do was to re-write that as $7^{60}2^{60} - 11^{60}3^{60}$. However, that doesn't really help. Next step is the ...
2
votes
1answer
36 views

Can you easily simplify large exponents without Fermat's Little Theorem?

I am asked to check if $x = 19$ is a solution to the following congruence: $$ x^{30034} ≡ 2 \pmod{18}$$ How can I do this? And in general, is there an easy/fast way to solve these types of problems ...
-1
votes
1answer
34 views

Calculating (a / b) mod p

I am basically calculating $^nC_r\bmod p$ where $p$ is a prime..... For large values of $n$ and $r$... As we know $^nC_r$ $$ \frac{n!}{r!(n-r)!} $$ I did a little study of calculating it, but I always ...
1
vote
4answers
77 views

Can anyone explain how to show that $n^{5} -n ≡0$ mod $30$ for every $ n \in \mathbb{N} $

I first tried to answer this using proof by induction, however my problem got more complicated when I got to the induction step. Is there another way of solving this problem?
0
votes
2answers
38 views

How do I find the modular inverse of $5^\space mod \space 26$?

I used the following formula to answer the question; $$\frac{((x∗k)+1)}{n},$$ where $x=(1,2,3...N)$. If the result of the formula is an integer then that result is the inverse to n mod k. In this ...
0
votes
1answer
15 views

n! mod c where c is a composite number

I am trying to write a program to calculate what is $n! \, \text{mod} \, c$, where $c$ is a composite number. While I understand $a b \, \text{mod} \, c$ is equal to $((a \, \text{mod} \, c) (b \, ...
0
votes
0answers
12 views

Can someone explain to me how to find the modular inverse of a number using the formula $\frac{((x*k)+1)}{n}$, where $x=(1,2,3…N)$?

I learnt online that if the result to the formula $\frac{((x*k)+1)}{n}$, where $x=(1,2,3...N)$, is an integer then that result is the inverse to n mod k. For example if I'm finding $5^{-1}$ mod 26 ...
1
vote
2answers
39 views

Solving congruence equations

Solve: $7x^6\equiv 11 \pmod{23}$ and $5^x\equiv 19 \pmod{23}$ I can solve simple congruence equations but how do I go about solving these?
0
votes
2answers
31 views

Which statements hold true for modular arithmetic?

I'm given a multiple choice problem with 4 statements that could be each true or false. To help determining which ones are true or false I did some example problems which I will list here. I have made ...
0
votes
3answers
33 views

Proving the GCD

Let $a= 16673011647$. Let $b = 16213295811$. Using the fact that $a \times −77566962 + b \times 79766315 = 51$, prove that $51$ is the gcd of $a$ and $b$. The part that is confusing is, using the ...