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
4answers
52 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
32 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
24 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
28 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
25 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
0answers
15 views

Question regarding a surjective function

The function $f :\mathbb{Z}_{12} \longrightarrow \mathbb{Z}_4$ is defined by $f(x)=3x$. I am asked given any $a,b \in \mathbb{Z}_{12}$ if preservation of addition and multiplication occur. I proved ...
0
votes
2answers
20 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
26 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
49 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
27 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
31 views

Getting higher powers in modular arithmetic

How would I solve $7^{\ 345}+4^{2313} \equiv x \pmod 3$ ?
1
vote
3answers
308 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
67 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 ...
-1
votes
0answers
15 views

Binomial equation in modular arithmetic

How to find solution $x$ for equation $(a+b)^c\equiv (a+b)^x \pmod{d}$ , where $a,b,c,d$ - some contants and $x \le c$
3
votes
3answers
104 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
19 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
184 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
38 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
63 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 ...
0
votes
1answer
22 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
26 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
5 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
30 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
34 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}$$ ...
0
votes
0answers
21 views

How to find p such that 1/p has a repeating decimal with a specified period

Alright, so I know a bit of information about the problem but I'm having trouble tying it all together. I know: if gcd(n,10)=1 then 1/n has a repeating decimal expansion. 10^3 = 1 mod p 1/p = ...
0
votes
3answers
36 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
25 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 ...
0
votes
3answers
19 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
40 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
51 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
49 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 ...
0
votes
0answers
47 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
26 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
0answers
15 views

Variant on the higher residuosity problem

This question is related to the Higher residuosity problem : given $ x^m\ \textrm{mod}\ n=r, \quad m>2$, and $ n=pq$, where $p$ and $q$ are large primes, if $m$ doesn't divide $p-1$, how easy is it ...
0
votes
2answers
68 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
18 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
19 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
35 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
96 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
23 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 ...
0
votes
0answers
18 views

Applying Modulo Operations to Exponents

Given $ gcd(h_1,h_2) = 1 $ $ s_1 = x^{h_1} mod\ N , s_2 = x^{h2} mod\ N$ $ x \ \epsilon\ Z^*_N $ and $h_1, h_2 \ \epsilon \ Z_N $ I'm trying to get $ x $ back from $s_1,s_2$. If I do ...
2
votes
1answer
45 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
36 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, ...
-1
votes
0answers
19 views

Finding remainders of numbers with multiple powers?

What will be the remainder of $30^{72^{81}} $ and how to solve this type of problem? Explain with an another example
0
votes
1answer
52 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
19 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
24 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 ...
2
votes
3answers
65 views

Modular Arithmetic - Quadratic Solutions Problem

I've just been given the following question in my crypto class, and I think I'm fairly sorted for it, but I was just wondering whether there might be any extra solutions to the ones I've worked out. ...
1
vote
4answers
86 views

Finding remainder when $32^{32^{32}}$ is divided by $7$

I recently learnt modular arithmetic for finding remainders when huge numbers are to be divided by some number. However, I am stuck at this problem: What is the remainder when ...
1
vote
2answers
41 views

Modular Arithmetic - Finding the smallest possible length of the room in inches

I need to know if I've done this proof correctly. Question: A rectangular room is to be tiled with square tiles. Consider only the length of the room. The tiles are available in 9-inch, 10-inch, or ...