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
32 views

Arithmatic on modular curves

I had tried to read the first few pages of Glenn Stevens's$\,$ Arithmetic on Modular Curves, but it is somehow extremely unreadable to me, the text format is odd and stating too much facts without ...
0
votes
3answers
33 views

Modulo arithmetic proof

Show that if none of the numbers in the list 1a,2a,..(p-1)a are congruent to 0 mod p, then no two numbers in the list are congruent to each other mod p. I am not sure how to try to demonstrate this. ...
16
votes
3answers
3k views

Why does (1/3) mod 3016 = 2011?

So I am taking a class where we are working on a cryptography section. Basically, the course says that: $$\frac 1 3 \mod(3016) = 2011$$ or when run through Python: $$\frac 1 3 \,\%\, 3016 = 2011$$ ...
1
vote
1answer
20 views

Is the set $V$ = { $([t], [g], [t], [j]): t,g,j∈$Z$,[2t+j] = [0]$} a subspace of vector space $(\mathbb Z_3)^4$?

Is the set $V$ = { $([t], [g], [t], [j]): t,g,j∈Z,[2t+j] = [0]$} a subspace of vector space $(\mathbb Z_3)^4$? I am inclined to think that it is a subspace. However, I cannot find any basis for the ...
0
votes
0answers
12 views

Way to evaluate sum of two set of modular square root.

I am wondering if there is a general way to calculate the following. Let $a, b, c, n$ be the integers and $p$ is the prime then, I am trying to evaluate $\left(\frac{a + \sqrt{b}}{c}\right)^n + ...
0
votes
1answer
24 views

Computing Large Number Modulo and Multiplicative Inverse

Prove that $3^{28}$ is a multiplicative inverse of $9^{34}$ modulo $17$, i.e. show that $3^{28}9^{34}\equiv 1\pmod {17}$. I really have no idea how to approach this example other than applying ...
1
vote
2answers
61 views

Analog clock with same hands - sometimes one can't tell time [duplicate]

There is an accurate analog clock, however both hands are the same size and shape. How many moments during a day a person can not conclude current time from the position of the hands? This is from a ...
0
votes
1answer
25 views

Quick question about mod equation

So here is the mod function: $$5 ^ {31} \cdot 2 ^{789} - 23^{23}\pmod{10}$$ Is there a way to shorten it, or I must calculate it plain numbers? I have tried the mod powers rule, but except for the ...
3
votes
3answers
46 views

Proving $93x + 47 \equiv 61 \pmod {101}$

I am preparing for an exam. I am dealing with this right now: $$93x + 47 \equiv 61\pmod{101}$$ However, I can't figure it out. Can someone describe steps for this example, or provide a link to any ...
-1
votes
1answer
20 views

How to prove this modular propositions [on hold]

Let $a$, $b$, $c$ be non zero terms in $\mathbb{Z}_p$ ($p$ is prime). $\operatorname{ord}(c)$ is the minimal natural number $r$ such as $c^r \equiv 1\pmod{p}$. 1) If $c^r \equiv 1 \pmod{p}$ and $c^q ...
0
votes
3answers
18 views

system of conguences

I am trying to figure out how to solve: Find $x, y \in \mathbb{Z}$ such that $$2x+y\equiv 4\pmod{17}$$ and $$5x-5y\equiv 9\pmod{17}.$$ I know this means $2x+y-4$ and $5x-5y-9$ are multiples of $17$, ...
-1
votes
1answer
29 views

Prove that $2n + m \equiv 0 \pmod3$if and only if $ n \equiv m \pmod3$ [on hold]

Prove that $2n + m \equiv$ $0 \pmod3$ iff $n \equiv$ $m \pmod3$ Is there a way to prove this without proving both directions of the biconditional?
2
votes
1answer
37 views

Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$. I am not even sure what tags to use because I am not sure of right methods to ...
1
vote
2answers
42 views

Summation Proof Dealing With 3s Multiples [duplicate]

So the problem is as follows: Prove that if the sum of digits of a decimal $n$ is three's multiple, then n is three's multiple by direct proof. For example, $11234567$ is 3's multiple because ...
-2
votes
0answers
52 views

Summation Direct Proof Help [on hold]

Prove that if the sum of digits of a decimal n is three's multiple, then n is three's multiple by direct proof. For example, 11234567 is 3's multiple because 1+1+2+3+4+5+6+7=24, and in fact, 11234567 ...
1
vote
2answers
38 views

Proving $10^n \equiv 1 \pmod 3$ for all $n\geq 1$ by induction

Prove that $10^n \equiv 1 \pmod 3$ for all positive integers $n$ by mathematical induction. Can someone please help me in solving this problem and explain what's going on? Any guidance would be ...
1
vote
1answer
26 views

Chinese remainder theorem to solve 3 mod 11 and 11 mod 13 [on hold]

Im trying to Decrypt a cipher text which has been encrypted using RSA and whose resulting value is 20. public parameters are N = 143 and e = 17 . I've gotten down to 3 mod 11 and 11 mod 13 and I've ...
-3
votes
3answers
74 views

How to show $20^3 \mod 11 = 3 \mod 11$? [closed]

How do I show: $$20^3 \mod 11 \equiv 3 \mod 11$$ I am very confused about this; please give a step by step way to solve this easily. Please don't use too much math jargon. Thanks
0
votes
0answers
28 views

Given $f=x^4+x+1 \in \mathbb Z_{2}[x]$ is primitive, write down an $m$-sequence ${a_n}$ associated to $f$

I'm not sure how to solve this question exactly. I know that the period will be 15 but I don't know how to construct the $m$-sequence.
1
vote
2answers
33 views

Existence of square root in $\mathbb Z_n$?

I had this question on my final exam and I struggled with it. It asks to prove or disprove the following: $$\forall m \in Z, \ \forall \ [a] \in Z_{m}, \ \exists \ [b] \in Z_{m}, [a]=[b]^{2} $$ ...
0
votes
1answer
28 views

The multiplicative group of integers modulo n

I need to write an introduction about the history who first showed that the multiplicative group of integers modulo $n$ is cyclic for certain $n$, when they showed it, why it was surprising, etc. ...
-1
votes
0answers
13 views

Modular Operations

Note: I am unsure how to properly format modular operations, so every operation here should be considered in its modular form. How do I do: $4*x-8=11$ in modulus set $11$?
1
vote
1answer
65 views

Find the multiplicative inverse of $5$ in $\mathbb Z_{73}$

I'm having some trouble with this question. The inverse should result in $44$ but I am getting $29$ $$73 = 14 \times 5 + 3$$ $$5 = 1 \times 3 + 2$$ $$3 = 1 \times 2 + 1$$ so $\gcd(73,5)=1$ using ...
-2
votes
1answer
19 views

Subgroups of $ \mathbb{Z}_n$ (integers mod $n$) [closed]

Is $\langle 15 \rangle$ a subgroup of $ \mathbb{Z}_{18}$ (the integers mod $18$)? There is a theorem in my book that says for every divisor $k$ of $n$, $\langle n/k \rangle$ is a subgroup of $ ...
2
votes
1answer
34 views

How to determine number of roots of $a^k + b^k \equiv c^k \pmod{d}$?

Is there a way to determine number of roots of $a^k + b^k \equiv c^k \pmod d$? It is an algorithmic task, not theoretic math. I am not looking for a closed formula.
0
votes
1answer
41 views

Number of solutions of the congruence $x^p \equiv x\pmod p$

How do I show that $x^p \equiv x\pmod p$ has precisely $p$ solutions? I can use Lagrange's theorem and Fermat's little theorem.
2
votes
2answers
37 views

Use Euclid's algorithm to find the multiplicative inverse $11$ modulo $59$

I was wondering if this answer would be correct the multiplicative of $11$ modulo $59$ would be $5$ hence $5\cdot11 \equiv 4 \pmod{59}$. Is this correct?
0
votes
0answers
19 views

Modulus Syntax in congruences

So I have some homework that has a notation I've never seen before and I can't find any documentation myself. Our professor gave us problems like this ...
0
votes
0answers
36 views

Solving RSA cipher without calculator

I have a question: Encrypt the message UPLOAD using RSA with $n=3\cdot 31$ and $e =17$. My question is, how can I solve this with a calculator and in an efficient manner due to being in an exam ...
2
votes
5answers
61 views

Possible solutions of a diophantine equation: $p^2+pq+275p+10q=2008$

What are couples of prime integers that verify this diophantine equation: $$p^2+pq+275p+10q=2008?$$ I tried to solve this equation trough the rules of modular-arithmetic. I rewrite the equation as: ...
0
votes
2answers
41 views

Factorization in modular arithmetic

Is this expansion a legal step? $12^8\mod15 = 2^8 * 2 ^ 8 * 3 ^ 8\mod15$
0
votes
0answers
44 views

Collatz algorithm generalization try-out (Collatz k-algorithm)

Recently I have been reading about the Collatz conjecture here in Mathematics Stack Exchange, and also found the fantastic paper of professor Lagarias about it. Everything was so interesting (and I ...
0
votes
0answers
20 views

Number of times the loop is executed

Initially I have provided x and y and the value of x and y repeatedly calculated until at some point the sequence is start repeating. ...
0
votes
2answers
25 views

Problem in proof of: Show the order $d$ of $a$ modulo $m$ exists and $d\mid\phi(m)$

Theorem: Let $m\in\mathbb{N}$ and $a\in\mathbb{Z}$ satisfy $(a,m)=1$. Then the order $d$ of $a$ modulo $m$ exists, and $d\mid\phi(m)$. Proof: By Euler's theorem, one has $a^{\phi(m)}\equiv ...
-1
votes
0answers
26 views

Modular Multiplicative Inverse of a Number

Modular Multiplicative Inverse for a prime M A^(M-1) % M = 1 From Fermat's Little Theorem Hence, A * A^(M-2) % M = 1 Or in other words, A^-1 % M = A^(M-2) % M ...
0
votes
2answers
32 views

Order of Elements in $Z_{12}$

So I know all the orders of the elements in $(Z_{12},+)$ $|[0]| = 1$ $|[1]| = 12$ $|[2]| = 6$ $|[3]| = 4$ $|[4]| = 3$ $|[5]| = 12$ $|[6]| = 2$ $|[7]| = 12$ $|[8]| = 3$ $|[9]| = 4$ $|[10]| = ...
0
votes
1answer
40 views

Number Theory proving questions [closed]

Let $n$ be a positive integer such that $n \equiv 3 \pmod 4$. Prove that $x^2 \equiv -1 \pmod n$ is not solvable for integer $x$.
8
votes
1answer
169 views
+100

Reduction modulo p of a linear group over the rational numbers

A paper (http://arxiv.org/pdf/1407.3158v2.pdf) contains the following theorem: Suppose $\mathbb{G}$ is a connected, simply connected, semisimple algebraic group defined over $\mathbb{Q}$, and let ...
1
vote
4answers
32 views

How to solve modular equations

How to solve modular equations? So for example $a \equiv i$ mod $x$, $a \equiv j$ mod $y$ for some given $i,j,x,y$ with $gcd(x,y)=1$, and I must find $a$ mod $x*y$. Any tips on how to do this? ...
2
votes
1answer
47 views

Adding mod Values

I have the expression $$\frac{1000}{2^k} - \frac{n \pmod{2^k} + (1000-n) \pmod{2^k}}{2^k}$$ I know that the value of the expression is an integer, and I suspect that it is $$\frac{1000 - \ell \cdot ...
0
votes
1answer
47 views

Example for $a^k\equiv b^k$ and $k\equiv j$ but $a^j\not\equiv b^j\pmod n$

I need some help in the number theory please , Who can give me an example : If $$a^k≡b^k \pmod{n}$$ and $$k≡j \pmod{n}$$ is not necessary to be $$a^j≡b^j \pmod{n}$$
0
votes
1answer
52 views

$a^2\equiv1 \pmod n$ iff $a\equiv\pm\,1\pmod p$ for all $p\mid n$

(Not)if $a$ is an integer and $n$ a postive integer, then $a\equiv\pm 1\pmod p$ for all primes dividing n if and only if $$a^2\equiv 1\pmod n$$ $\Longrightarrow $ is wrong,Tonyk note ...
9
votes
1answer
77 views

Solving a Diophantine equation: $p^n+144=m^2$

I found this Diophantine equation: $$p^n+144=m^2$$ where $m$ and $n$ are integers and $p$ is a prime number. I solved it but I want to know if there exist other proofs through the use of rules of ...
0
votes
0answers
23 views

Define the concept of square root (mod n)

So i was looking at some of the past papers of my module, the new module has different topics slightly.I was wondering how would you solve this since we didn't cover such topic this year Define the ...
2
votes
0answers
44 views

Are there Latin squares with no repeats on the diagonal not of the form 2y+x+1(mod n)?

I am looking for a certain kind of latin square (nxn). Rules: No repeats in any column or row (Definition of Latin Square) No repeats in any diagonal including others than the main diagonal. So ...
1
vote
1answer
17 views

prove a function is not one-to-one

Let us look at the field $\mathbb{F}_{p}=\{0,1,2,...,p-1\}$ for a prime number p. And let $f:\mathbb{F}_{p}\rightarrow \mathbb{F}_{p}$ be the function given by $f(n)=n^2 \space (mod \space p)$. How ...
0
votes
0answers
88 views

Find 3 integers x so that 271x ≡ 272 (2015)

Now I found the gcd(2015,271) = 1 when (2015)(-62) + (271)(461) For my first integer, I tried doing this -> x ≡ 272 * 461 (mod 2015), and 2015| x + 125392, then I get x = 127407 And then x ≡ ...
1
vote
3answers
27 views

What is the following expression simplified to?

$$x \mod 1000 \mod 5$$ I would have thought that it was $x \mod 5000$ except that it doesn't hold true for $x = 5005$ since you'll get zero, but $5005 \mod 5000 = 5$.
0
votes
1answer
10 views

Solving a congruence with an invertible piece

If I have $$a \equiv bp^k \bmod p^e$$ for $0 \leq k \leq e$ with $a,p,k,e$ known. How do I solve for $b$ given that $b$ is invertible?
0
votes
2answers
40 views

Hensel’s Lemma Number Theory Confusion

I have been given an example, finding the solutions of the congruence $f(x) ≡ 0$ (mod $5^4$) for $f(x)=x^2+1$ This solution finds that for mod $5$ we have $x_0=2$ . So through the 'lifting' process, ...