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
4answers
44 views

Inverse $2^{18}$ in GF(23) without extended euclidean algorithm

I have a little question about the calculation of the inverse of $2^{18} \mod\ 23$. I have the solution of this: $$ \text{The inverse of $2^{18}$ is $2^{-18}$. The modulus in the exponent is ...
0
votes
1answer
36 views

Explanation and validation of point adding/doubling on elliptic curves

I'd like to implement point multiplication on elliptic curves over prime fields. My problem is that I've found different definition how to do it. At adding: the second parameter of the result is not ...
1
vote
2answers
90 views

prime powers modulo prime

I stumbled upon the following property: $n\equiv n^5\bmod 5$ for all $n\in\mathbb{Z}$, so out of I tried other (prime) numbers $n\equiv n^p\bmod p$. My question is whether this is true for all primes ...
0
votes
1answer
362 views

Solving mod congruence

So i have a problem like this 34x ≡ 77 (mod 89) This is how i try to solve it but it doesn't seem to work :( If anyone can give me a hint on how to proceed from ...
0
votes
3answers
72 views

Discrete mathematics. Just an impression, or this is always true?

I feel that the following is always true: $$ \frac{2^k-1}{3} \equiv 1 ~(\text{mod }2) \text{ if }k \equiv 0 ~(\text{mod }2) \wedge k \geq 2$$ I've just tried it using a "brute force" approach, but ...
2
votes
1answer
31 views

modulo of 2 polynoms

I'm trying to understand the example given in the wikipedia explanation of the algorithm of Reed Solomon: http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction. We have $p(x) = 3x^6 + ...
2
votes
4answers
225 views

Proving congruence modulo, number theory

The task is to prove $24^{31}\equiv 23^{32}\pmod {19}$. I'm trying to use Fermat's little Theorem and so far I only found that $24^{31}\equiv 19\pmod{19}$. Would proving that $17\mid23^{32}$ prove ...
0
votes
2answers
67 views

Solving modular arithmetic equation.

Need help! I'm having some problem with understanding this equation! We have a similiar example in the book, but I dont really get what they mean. So here is the question. Given 3u = 1 (mod 5), find ...
1
vote
1answer
30 views

Question about multiplication of modulars

Why is the property when you multiply two modulars (you multiply the two ones on outside and the two ones inside) Why does that property hold true? Addition is easy but multiplication doesn't make ...
0
votes
1answer
37 views

Congruence and modular arithmetic

$228,547,866$ divided by $q$ leaves the remainder of $r$. Find $r+q$. The problem is designated to be solved by using modular arithmetic. Even though I haven't learned what that is.
0
votes
1answer
53 views

GCD of polynomials

In $\mathbb{Z}/5\mathbb{Z}[x]$ use the Euclidean Algorithm to find the GCD of $x^4+x^2$ and $x^4+x^3+3x$. My thoughts: I am getting to the point where I need to use a fraction to get further in ...
0
votes
2answers
88 views

Finding unknown in modulo operation

I have this question on a test 1) find d=gcd(77,50) using euclidean alg. 2)find s and t such that 77s+50t=d 3) use these results to find x such that 50x=4(mod77) Note:the qual sign should have 3 ...
0
votes
1answer
50 views

Rules on surjective and Injective

So I am trying to prove $f([a]+[b]) = f([a]) + f([b])$ for $\mathbb Z$ mod $12$ and the same for multiplication... Can you show that this is true based on a function being surjection and injective ...
0
votes
0answers
59 views

Modular arithmatic

Suppose that f : Zmod12 -> Zmod4 is defined by f [x] mod 12 = [3x]mod 4 where the subscript indicates the appropriate modular arithmetic. (A) IS f surjective? (B) is f injective? (C) let [a], [b] be ...
1
vote
1answer
50 views

Proving modulo equation with x-power

I'm trying to prove following equation: $$ (g^{y} \mod n)^x \mod = g^{xy} \mod n $$ I tried many multiple approaches, all of them failed, and there is waaay too much of them to write them here, so I ...
0
votes
1answer
37 views

Getting higher powers in modular arithmetic

How would I solve $7^{\ 345}+4^{2313} \equiv x \pmod 3$ ?
1
vote
3answers
629 views

Find the smallest positive integer x such that 2015! ≡ x (mod 2017)

Q. The next year that is a prime is 2017. Find the smallest positive integer x such that 2015! ≡ x (mod 2017). So, this is what I have; By Wilson’s theorem, (2017-1)! ≡ -1 (mod 2017) ⇒ 2016! ≡ -1 ...
4
votes
2answers
75 views

Generalization of $n$ mod $2 = \dfrac{1-(-1)^n}{2}$

I had this idea that $n$ mod $2 = \dfrac{1-(-1)^n}{2}$ for $n \in \mathbb{N}$. Are there any generalizations for this? For example for $n$ mod $3$ etc.? I would prefer some answers containing basic ...
3
votes
3answers
167 views

Prove that the equation $x^3 + 10000 = y^3$ has no solutions

The below question was given in my workbook for number theory. I have seen the solution, and it utilizes $\mod 7$, but I am unsure of why $\mod 7$ was chosen to solve the problem. Would any number of ...
1
vote
1answer
34 views

modular arithmetic problem (when solving elliptic curves)

Given E: (elliptical curve) $y^2 = x_3+2x+2 \bmod 17$ Recall: $y^2 = x^3+ax+b$ point $P=(5,1)$ Compute: $2P = P+P = (5,1)+(5,1)= (x_3,y_3)$ Now the formula used here is slope $m = \dfrac{3x_1^2 ...
10
votes
2answers
291 views

Are integers mod n a unique factorization domain?

I am trying to learn abstract algebra from scratch, jolly stuff, but in the process of doing so this puzzles me: Having a ring of integers mod n, where $n=pq$ is composite, as I understand we have ...
0
votes
0answers
65 views

RSA Decryption - finding Private Key

Let p and q be primes and $e \in \mathbb{Z}^+$, with $\gcd (e, (p-1)(q-1)) = 1$. Let d be the inverse of $e \mod (p-1)(q-1)$. The decrption process where M is plaintext and C is ciphetext ...
1
vote
3answers
181 views

Find a number congruent to mod

Can anyone give a hint of how to go about solving this? Please don't give answer thanks Find the integer a such that ...
1
vote
1answer
65 views

Negative quotients and their remainders

Since $16 \div{-3} = -5.\overline{3}$, I thought I could also express this as $16 \div{-3} = -5\:R\:1$ or in other words $16\mod{-3} = 1$. My calculator tells my it is in fact $-2$. Along the same ...
1
vote
2answers
199 views

Multiplication of residue classes modulo n

If $\bar{a}$ and $\bar{b}$ are residue classes modulo $n$, it is straightforward to see that $\bar{a} \bar{b} = \overline{ab}$. But given that those classes are sets, does the $=$ mean set equality? ...
0
votes
1answer
45 views

Calculate power of large numbers mathematically?

Is there a short-hand method to find the value of a number with a large power. For example : 1024^2048
1
vote
1answer
38 views

Proof that 6 divides $a \in \mathbb{Z}, a(a^2 - 7)$

I am trying to prove a question from my tutorial sheet, is this an acceptable proof? Six cases exist: $$a,k \in \mathbb{Z}, a(a^2 - 7) = 6k \\\text{Proof:}\\ a = 0 \mod 6 \longrightarrow a^2 = 0 \mod ...
2
votes
2answers
90 views

Last decimal digit of any perfect square must be $0,1,4,5,6$ or $9$

Last decimal digit of any perfect square must be $0,1,4,5,6$ or $9$ My Proof: Ten cases exist, yielding the following equalities: $$(1\mod{10})^2 = 1\mod{10}$$ $$(2\mod{10})^2 = 4\mod{10}$$ ...
-1
votes
3answers
38 views

Finding $-8$ in $\Bbb Z \pmod 5$

This is a very simple question but what is $-8$ in $\Bbb Z \pmod 5$? I am looking for a positive number. I know $5 \times 2 = 10$ so it is either $2$ or $-3$. I assume I am just looking at it a ...
0
votes
1answer
30 views

How can we prove that we can get any $f$ modulo a prime $p$, that satisfies these equations?

We can suppose that we have four naturals not equal to zero: $a, b, c, d$. Further, we're working modulo a prime $p$. Now if we find $a, b, c, d$ that satisfy: $$f \equiv a \cdot c \equiv b \cdot d ...
2
votes
6answers
908 views

Is this it a theorem that numbers congruent modulo two relatively prime $m,n$ are congruent modulo $mn$?

"If $a \equiv b \pmod m$ and $a \equiv b \pmod n$ and $\gcd(m,n)=1$, then $a \equiv b \pmod {mn}$ " Is that a true theorem? I can't find it in my textbook!
-3
votes
2answers
226 views

How can I solve $4x + 51y = 9$ using congruences?

I'm given: $4x+51y=9$. I am given a hint that when we use $4x=9 \pmod{51}$ we get $x = 15 + 15t$, and also if we use the congruence $51y=9 \pmod 4$ we get $y=3+4s$. They say it's handy to then find ...
0
votes
3answers
25 views

Modular Equivalence

Prove that if a and b are integers such that a|b and b > 0, then (x mod b) mod a = x mod a for any x. Solution: As a|b, we have b = pa for some integer p. Let x mod b = r, then we have x = bq + r = ...
1
vote
1answer
105 views

Modular Arithmetic - Changing a Congruence Modulo Relation

Here the solution for $27^{17} \pmod{15}$ is shown. Why is $27 \equiv 12 \pmod{15}$ rewritten as $27 \equiv -3 \pmod{15}$? What is the logic/proof?
2
votes
1answer
109 views

Solutions for $x^2+y^2=2007$ and reference request.

I have never formally studied number theory, it is not a part of my course work, and what I have learnt is reading Wikipedia or the answers here. This question was on a test and I tried to use ...
1
vote
2answers
84 views

Chinese remainder theorem?

In the 2014 AIME 1, number 8 says: The positive integers $N$ and $N^2$ both end in the same sequence of four digits $abcd$ when written in base 10, where digit $a$ is not zero. Find the three-digit ...
1
vote
0answers
72 views

Fermat's Little Theorem not useful as $p\rightarrow\infty$

I'm having trouble with some questions of which Fermat's little theorem doesn't seem to simplify enough. For questions such as What is $10^{41} \text{mod}\;49$? I get stuck. Since ...
1
vote
0answers
31 views

Mistake involving Chinese remainder theorem

I ran into a snag in attempting to solve the following problem. $$x\equiv r\pmod p$$ $$x\equiv0\pmod q$$ I did the following $$x=k_1q=k_2p+r$$ $$k_1q\equiv r\pmod p$$ $$k_1\equiv rq^{-1}\pmod p$$ ...
0
votes
3answers
106 views

If the sum $\sum_{x=1}^{100}x!$ is divided by $36$, how to find the remainder?

If the sum $$\sum_{x=1}^{100}x!$$ is divided by $36$, the remainder is $9$. But how is it? THIS said me that problem is $9\mod 36$, but how did we get it?
0
votes
2answers
72 views

What is $25^4 mod 39$ congruent to?

My result is $25^4 \equiv 25 (\textrm{mod}\ 39)$, but Wolfram Alpha simplifies $25^4 \ \textrm{mod}\ 39$ as 1. How should I interpret this? I have the following ...
-1
votes
1answer
23 views

Turn formula with remainder

How do I turn these formulas: $$\begin{align} y &= \left\lfloor\frac{ x \mod 790}{10}\right\rfloor + 48 \\ z &= (x \mod 790) \mod 10 + 10\left\lfloor\frac{x}{790}\right\rfloor + 48 ...
1
vote
1answer
21 views

Finding solutions belonging to given field

So I am preparing for a weekly test at my uni and I have a problem like this: Find the solutions of the equations in fields $Z_7, Z_{11}, Z_{13}$. And I'm thinking about the approach for solving ...
0
votes
3answers
129 views

Is modulus a periodic function?

Is taking a mod of something, like 12 mod 2 (which is 0), a periodic function? If not, what kind of function is it and can it be classified as such?
2
votes
3answers
121 views

what is the remainder if we divide $72^{200}$ by $5$?

What is the remainder if we divide $72^{200}$ by $5$? I am very new to modular arithmetic! Please help!
0
votes
2answers
53 views

Reducing exponents mod n

Say I have 5^(52) mod 22 How do I reduce this? I know if 22 was a prime number, then I could simply I could simply reduce 5^(22) * 5^(22) * 5^(8) which would become 5^(8) mod 22 but that doesn't ...
2
votes
1answer
98 views

Combining results with Chinese Remainder Theorem?

$9x^2 + 27x + 27 \equiv 0 \pmod{21}$ What is the "correct" way to solve this using the Chinese Remainder Theorem? How do I correctly solve this modulo $3$ and modulo $7$ without brute force?
0
votes
2answers
59 views

Do we not have to follow Euclidean division strictly when doing modulo operations?

Referring to this earlier question of mine, and in particular, the answer of Yiyuan Lee, we have that $(p-1)\equiv -1 \pmod p$, since we have that $(p - 1) : p = 1$ with a remainder of $-1$. However, ...
0
votes
1answer
139 views

Convert modulo 65 into modulo 26.

Is there anyway to convert x ≡ 9 (mod 65) into x ≡ something (mod 26)? Generally is there a way to convet one modulo into some other modulo?
0
votes
1answer
34 views

Proving that $mx \equiv 0 \pmod n$ has $\gcd(m, n)$ solutions in the interval $[0, n-1]$

I wish to prove, using my own intuition, that there are $\gcd(m, n)$ group homomorphisms from $\mathbb{Z}_m$ to $\mathbb{Z}_n$. I have reduced(?!) the problem to proving that there are $\gcd(m, n)$ ...
2
votes
1answer
27 views

How do I calculate the number of times angle X should be added to obtain angle Y?

Suppose I have a angle X=100 and angle Y=60. when we add X 15 times it gives ...