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

1
vote
3answers
37 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
14 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
15 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$, ...
0
votes
0answers
8 views

Fast modular trace of matrix exponentiation using Fermat's little theorem for matrix

The question might be related to http://stackoverflow.com/questions/12268516/matrix-exponentiation-using-fermats-theorem but is slightly different as I only concentrate on the trace of the matrix. I ...
-1
votes
1answer
28 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
41 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
47 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
36 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
24 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
72 views

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

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
27 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
32 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
25 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
12 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$) [on hold]

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
34 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
18 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
35 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
53 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$.
5
votes
1answer
146 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
76 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 ...
1
vote
1answer
36 views

Prove that $a^{i}=b^{j}$ if and only if $i\equiv{j}\pmod{n}$ [closed]

Let $(G, *)$ be a Group, $a\in{G}$, and $O(a)=n$. Why is $a^{i}=b^{j}$ if and only if $i\equiv{j}\pmod{n}$?
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
41 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, ...
2
votes
3answers
48 views

If $x^2\equiv a\pmod n$, then $(n-x)^2\equiv a\pmod n$

Given that $x$ is a solution to $x^{2}\equiv a \pmod n$, show that $y=n-x$ is also a solution. Please don't solve, just give me a hint.
-1
votes
6answers
81 views

Solve for $x$ in the congruence $2x \equiv 7\pmod{17}$ [closed]

Solve for $x$ in the congruency $2x \equiv 7\pmod{17}$. I know this should be fairly easy.. I just don't know the steps.
5
votes
4answers
50 views

Find $n\bmod 8$ when $n\bmod 56=29$

A number when divided by $56$ gives the remainder $29$. If it is divided by $8$ then what will be the remainder? Sorry if this is a stupid question, but I'm studying to improve my math.
0
votes
1answer
22 views

Show that $n\bmod m$ is periodic $\forall n,m \in \mathbb{N}^+$

How can I show that $n\bmod m$ is periodic? If I have a simple example like $n\bmod6 \equiv a$ how can I show that this is periodic if e.g $f(n) = n\bmod6$?
-1
votes
2answers
55 views

Find remainder of $3^{12} + 5^{12}$ when divided by $13$ [closed]

What is the remainder when $3^{12} + 5^{12}$ is divided by $13$?
0
votes
1answer
44 views

How can I calculate $d$ from this equation?

So how can I calculate $d$ from this equation : $17^d \mod 55 = 8 $ ? I am solving an RSA Encryption question and im confused on how the modula is formulated when transferring to the other side, and ...