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

Trouble with substitution in modular arithmetic.

I was watching a video on the Diffie-Hellman key exchange, and they did: $$12 ^{15}\bmod \ 17 = 6 ^{13}\bmod \ 17$$ because $$3 ^{13}\bmod \ 17 = 12$$ So he substituted $3^{13}$ in for $12$. $$3 ...
0
votes
0answers
12 views

Calculate modular inverse

I have the following exercise Let us assume that a little bird had told us m, the generator's modulus, and we know that m is prime. Then we can recover a and c from just three consecutive ...
0
votes
1answer
25 views

Meaning of mod (-$\pi, \pi$]

Example: $Arg(\frac{-1-i}{i})=Arg(-1-i)-Arg(i)=-\frac{3\pi}{4}-\frac{\pi}{2}=-\frac{5\pi}{4}=\frac{3\pi}{4} (mod (-\pi, \pi])$ What is the meaning of $(mod (-\pi, \pi])$ and why does it make the ...
5
votes
4answers
754 views

Why is it more efficient to compute the modular exponentiation by calculating to the power of two and not three for example?

I learned about modular exponentiation from this website and at fast modular exponentiation they calculate the modulo of the number to the power of two and then they repeat this step. Why not ...
1
vote
2answers
107 views

How to prove that every power of 6 ends in 6?

Yesterday I had the traditional math matriculation exam, and in it there was a question "In what digit does the number $2016^{2016}$ end in?" After the test The Matriculation Examination Board ...
2
votes
2answers
64 views

Show that $p^2 = 1\pmod {24}$ [duplicate]

Given $p$ a prime number such that $p \geq 5$ Show that $p^2$ is congruate to $1$ modulo $24$ This is what I tried : We have $p^2$ congruate to 1 modulo $3$ because if $p=3k+2$ so p is congruate to ...
0
votes
1answer
15 views

Euclid's Extended GCD Inverse [closed]

I'm trying to make sense out of this table. I understand the $k,j,q$, and $r$ part but I don't understand how they get the $x$ and the $Y$. Any and all help is much appreciated!
0
votes
1answer
37 views

Intuition why $(ab \mod m) = (a\mod m )\times( b\mod m) $

I've had quite easy time imagining why addition would be 'persistent'$\mod m$ but with multiplication it's not that obvious. I've seen proofs of it, but none have helped me internalise it. Any tips on ...
0
votes
1answer
44 views

Calculate $59x^{-1}\equiv 1 \pmod{63}$ [closed]

How can I calculate $$59x^{-1}\equiv 1\pmod{63}?$$ I only know that $59$ is prime.
-1
votes
1answer
15 views

Find integer solutions to x being an element in an equation

We began the topic of Cryptography in our Discrete Math class and for our first homework assignment, we were given the following problem: Find all integer solutions to x $\equiv$ 3 (mod 6) How would ...
7
votes
2answers
88 views

Proof by induction, utilizing inductive assumption

Show that for every natural number $n$ there exist integers $x,y$ such that $$4x^2 + 9y^2\equiv 1\pmod{n} $$ The base case is trivial, since 1 divides anything. Assume the claim holds for some ...
3
votes
4answers
75 views

If possible, solve $7x^2 - 4x + 1 \equiv 0 $ (mod 11)

If possible, solve $7x^2 - 4x + 1 \equiv 0 $ (mod 11) Not sure if I'm approaching this problem correctly, any help is appreciated. So far I have: $7x^2 - 4x + 1 \equiv 0 $ (mod 11) $21x^2 - 12x + ...
1
vote
1answer
62 views

If possible, solve $3x^2 + 6x + 5 \equiv 0 $(mod 539)

If possible, solve $3x^2 + 6x + 5 \equiv 0 $(mod 539) I am struggling with several problems just like the one above, and decided to post what I believe is the hardest one to hopefully able to do ...
0
votes
1answer
27 views

How do I find the solutions of the congruence $3x^3-2x^2+x \equiv0\mod{30}$?

How do I find the solutions of the congruence $3x^3-2x^2+x \equiv0\mod{30}$? If someone could walk me through a solution so I can then attempt and do all of my other examples that would be fantastic. ...
1
vote
0answers
29 views

Why does $\equiv 1\ (\text{mod}\ n)$ seem so important?

I'm not great with math so please feel free to correct any mistakes in my question (or add more examples). I'm a software engineer and have recently wanted to better understand the maths behind RSA ...
1
vote
1answer
25 views

Finding modular inverse (wrong approach)

I'm trying to find the modular inverse of $$30 \pmod{7} $$ I have tried using the Euclidean algorithm and it gave me the right answer, which is $x \equiv 6 \pmod{7} $. However, I tried using another ...
1
vote
1answer
29 views

Substitution with modular arithmetic?

I was watching this video, and was curious how they were able to do the following: $$m^e\ modN = c$$ $$c^d\ modN = m$$ Therefore, $$m^{ed}modN = m$$ It's all simple algebra, but I wasn't sure how ...
0
votes
1answer
22 views

Determining order of an element

Let $n$ be the smallest integer such that $a^n \equiv -1 \ (mod \ m)$ Show that $ord_m(a) = 2n$ My proof says that, if there exists an integer $k$, with $k<2n$ then $a^{2n} \equiv a^k \ (mod \ ...
1
vote
1answer
28 views

Modulo Arithmetic - Find smallest divider greater or equal to.

I'm looking for a nice solution to the following problem: x mod(y + d) = 0. Where x is a positive integer and y is a positive integer smaller or equal to x. I'm looking to find the smallest d ...
0
votes
4answers
53 views

Discrete Mathematics - Congruence [closed]

Prove that there does not exist $n \in \Bbb N$; such that $n \equiv 2 \pmod 4$ and $n \equiv 4 \pmod 8$.
1
vote
2answers
17 views

Do wrapping diagonals on Word Searches contain all letters?

Given an example, 3x3 word search grid as follows: $\begin{bmatrix}A & B & C\\D & E & F\\G & H & I\end{bmatrix}$ We use a zero-based index and elements are identified by ...
2
votes
1answer
35 views

Is it possible to (uniquely) reverse modulo operation by solving multiple equations with the same original integer?

I've tried searching but I haven't been able to find an answer. There are similar questions about reversing modulo operation here on stackexchange, but I haven't found a question which is applicable ...
1
vote
4answers
41 views

is it possible to equate/express what a and b is from $a^b\pmod n\equiv x$

I'm recently started learning modular mathematics as part of an advanced cryptology unit. It's relatively new to me. I'm trying to find out how to express/determine a,b given $a^b\pmod p\equiv x$ , ...
4
votes
1answer
440 views

If more than one prime number satisfies a given congruence, must an infinite number of primes satisfy that congruence?

I understand that this is kind of a broad question, but if no affirmative proof is known, can anyone give a counterexample?
1
vote
1answer
101 views

I'm a new to modular maths and I need to find 'a' given $(x+y)^p \equiv a^b+c^d\pmod p$

I'm new to modular maths and I've been asked to do the following: given p is prime and $(x+y)^p \equiv a^b+c^d\pmod p$ , find a=?,b=?,c=?,d=? Can anyone help me with the same? Or atleast point me in ...
0
votes
1answer
31 views

What are the solutions to this equation (primes, modular arithmetic)?

Given: $m,n\in\mathbb{N}$ and $p$ is prime. Find the solutions to the following equation: $$m^2-3mn+(np)^2=12p$$ Thank you in advance.
0
votes
2answers
35 views

Proving a subgroup is cyclic

Let $G=Z_n$ for $n\gt1$ and let $a,b \in G$ where $a,b$ are two integers (with at least one nonzero). Prove that the subgroup of G generated by $a$ and $b$ is indeed cyclic and is generated by $c \in ...
0
votes
3answers
60 views

Calculate $2^{48} \equiv x \mod 140$

I've calculated the following equation and I've got this: Does there exist an easier solution?
3
votes
1answer
51 views

Is $x^2 ≡ 295$ (mod 2717) solvable?

Is $x^2 ≡ 295$ (mod 2717) solvable? -Having a tough time with this problem, currently covering a section on Quadratic Reciprocity Law of Gauss. After coming back to my professor, his hint was to ...
3
votes
2answers
67 views

weird relation modulo

This is going to sound like a stupid question, but I cannot understand how I get this result (I understand why, but it looks like there is no relation). $p, q$ primes why do we have this? $p \cdot ...
1
vote
0answers
36 views

Is it possible to show that there are integer solutions $n,m$ for $10^m+10^n+1\equiv 0$ (mod $q$) for a prime $q$?

I came across to this question: Prime numbers are related by $q=2p+1$ I have almost figured out the answer, but got stuck at the final step to show the following: For prime numbers $p,q$ that ...
0
votes
2answers
35 views

Modulo arithmetic with large numbers

I'm in high school and writing a paper on the mathematics behind RSA encryption. I now have come to the point where I have to solve: $50^{61} \pmod{77}$ Then, as on ...
0
votes
4answers
42 views

How to compute $3^9 \pmod {10}$

The solution given was: $3^9 = (27)^3 = 7^3 = 49(7) = 9(7) = 63 = 3 $ I understand up to $\ 3^9 = (27)^3 $ But after that I am lost. Can someone explain how to solve this and what is going on ...
0
votes
1answer
24 views

Modular Arithmetic Exponentiation Rule [closed]

Just wondering how one would go about using the exponentiation rule for modular arithmetic?
0
votes
1answer
27 views

Encryption and Decryption with RSA Coding

I have been given $N=2021$ and $E=5$. I am to encrypt the the word 'he' where h is 18 and e is 15. Then I am to find D, and k, and decipher the encrypted message. My first question is whether i do h ...
1
vote
0answers
37 views

Notation error in modular arithmetic problem

My calculus teacher recently gave us a problem concerning number theory. It was to find the error in $$ 10\equiv 3\pmod 7 $$ Apparently the error is the notation - there is a way to rewrite this ...
1
vote
2answers
71 views

Prove $f(a)-f(b)=n(a-b)$ and what is $n$?

I think that the following formula is true if $f(x)$ is a polynomial and $\pm n=0,1,2,3,\dots$. $$f(a)-f(b)=n(a-b)\tag1$$ I start off noting that it reminds me of the Fundamental Theorem of ...
-1
votes
1answer
98 views

What is the remainder when $2^{2^{517}}$ divided by $23$? [duplicate]

What is the remainder when $2^{2^{517}}$ divided by $23$? I tried Fermat Little theorem, and seems like I cannot make a further step. The trick here is about $2^{517}$ which does not follow the normal ...
1
vote
2answers
34 views

Discrete math: find prime number which solves the following conditions

Find prime number $p$ and polynomial $f$, so that the ring $F_p[x]/(f)$: 1) contains non-zero element $w$: $w^n=0$ for some $n$ 2) doesn't satisfy 1), but is a field 3) is a field which contains ...
0
votes
0answers
23 views

induction in congruence modulo

I am learning proof by induction in my math class and I am having trouble with this problem dealing with congruences. Let $s$ be a positive integer. Then $X \equiv \{a,b,c\} \pmod{2^sk}$ implies $X ...
0
votes
0answers
36 views

Showing a sequence is coherent

For my question, I am considering $p$-adic numbers, where $p$ is a prime in $\mathbb{Z}$. A sequence $(x_k)$ is coherent if $x_{k+1} \equiv x_{k}\ (mod\ p^k)$ for a prime, $p$, and natural number $k ...
0
votes
1answer
35 views

Solutions to a Modular Congruence

I am trying to find all integer solutions to the modular congruence $5x^7+x^2+2x \equiv 2\pmod {28}$ I broke it up into 2 cases: that is $\pmod 2,\pmod 7$. Using the laws of congruence and Fermat's ...
0
votes
1answer
13 views

System of congrences

If $m$ is an odd integer and $n \in \mathbb N$, prove that the system of congruence $2x \equiv 2n (mod\, m)$ $x \equiv m(mod \, 2^n) $ has exactly one integer solution $x$ with $0 \le x \lt 2^nm$ ...
59
votes
3answers
1k views

Mathematicians shocked(?) to find pattern in prime numbers

There is an interesting recent article "Mathematicians shocked to find pattern in "random" prime numbers" in New Scientist. (Don't you love math titles in the popular press? Compare to the source ...
1
vote
1answer
32 views

RSA Coding Question

I have been given that N=143 and the encoder E=7. An encrypted message 48 was received. I have to find the decoder and use it to compute the original message. This is how I did it but i'm not sure if ...
0
votes
0answers
30 views

Solving a polynomial with modular arithmetic.

$x^5+ax^4+bx^3+cx^2+dx+e=0$ Assume that $a,b,c,d,e$ are not arbitrary and that they are known. I was wondering if it were possible to reduce or 'simplify' this using some modular arithmetic. It ...
0
votes
0answers
20 views

calculate nCr given (n-1)C(r-1) under a modulo fast

Let $_nC_r$ be n choose r or $\frac{n!}{(r!*(n-r)!)}$ Given the value of $_nC_r$ for some n, r, equal to k, how could one find $_{n+1}C_{r+1}$ (mod m) fast computationally (small asymptotic time). ...
0
votes
0answers
12 views

Is Congruence Class an example of Equivalence Class? (Understanding the definition through Examples)

Would you say a congruence class such as $[0]_{4}, [1]_{4}, [2]_{4},$ and $[3]_{4}$ an example of Equivalence classes since: the set of all elements of $\{..., -8, -4, 0, 4, 8,...\}$ is related to ...
0
votes
0answers
36 views

I'm stuck on a proof involving the of Axiom for multiplicative inverses and modular arithmetic.

I am trying to show that the axiom of multiplicative inverses holds on sets of integers modulo P when P is prime. i just need to show that for any non zero integer, n less than P there is a unique ...
0
votes
1answer
29 views

Help with disproving one of the axioms in a modular arithmetic

I'm asked to prove that the axiom of multiplicative inverse doesn't hold in $$(\mathbb{Z}_{9} ,\times _{9},+ _{9} )$$ That is mod9 arithmetic (im not sure if im using the correct expression for that). ...