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
0answers
20 views

Modulo composite problem

With $k$ strictly positive integer, we define the sets $A_k\subset\mathbb{N}$ : $$\begin{array}{rl} A_k = \lbrace m& \equiv 5k-1 &\pmod{6k-1}\rbrace\\ \cup \lbrace\lbrace m& \equiv ...
0
votes
1answer
21 views

Modulo pattern with zero skipped

Is there a way to find a modular partern in which 0 doesn't exist. For eg : mod(x,6) 012345012345.... I'd like : 1234512345.... I need it for a rotation in a list but I cant use 0 Thanks !
1
vote
0answers
41 views

More efficient RSA using Chinese Remainder Theorem

Is there a way to increase the efficiency of the RSA algorithm by incorporating elements of the Chinese Remainder Theorem?
1
vote
4answers
80 views

Determine whether $x^2 - 14x + 30 \equiv 0$ mod 1615 is solvable. If so, find its solutions…

Determine whether $x^2 - 14x + 30 \equiv 0\pmod{1615}$ is solvable. If so, find its solutions. I assume the best way to solve this is via Chinese Remainder Theorem, but first i would have to break ...
1
vote
0answers
36 views

Solving $x^2\equiv b \mod p$ for $p$ prime

How do I go about solving $x^2\equiv 116 \mod 587$ for $x$? I know that 587 is prime. How would I get started? I know $116= 2^2\cdot 29$ I think if I can solve $116^{147}\mod 587$, then I will have ...
1
vote
2answers
40 views

If $a \equiv b$ mod n, then $ac \equiv b(c+n)$ mod n

Show that $a\equiv b$ mod n implies that $ac \equiv b(c+n)$ mod n. My proof attempt: If $a \equiv b$ mod n, then $n|(b-a)$ which implies that $(b-a) = nx$ for some $x \in \mathbb{Z}$. Which ...
0
votes
2answers
56 views

How do I factor $670726081$ if I have the informations that $33335^2\equiv670705093^2 \pmod{670726081}$?

How do I factor $670726081$ if I have the informations that $33335^2\equiv670705093^2 \pmod{670726081}$? I know that $\gcd(33335+670705093,670726081)$ is a nontrivial factor of $670726081$
1
vote
1answer
38 views

show that $3^{1974} + 5^{1974} \equiv 0 \bmod 13$

show that $3^{1974} + 5^{1974} \equiv 0 \bmod 13$ My attempt with this question was to use Fermate Little's THM. But I do not understand how to properly use it for this question. Can some one show me ...
0
votes
1answer
13 views

$a^2\equiv b^2\pmod n$ and $a\not\equiv \pm b\pmod n\implies\gcd(a+b,n)$ is a factor of $n$?

Suppose $a^2\equiv b^2\pmod n $ and that $a\not\equiv \pm b\pmod n$. How to then show that $\gcd(a+b,n)$ is a (nontrivial) factor of $n$? Hint to get started please.
1
vote
2answers
38 views

Proof of $[(a \; \text{mod} \; n)+(b \; \text{mod} \; n)] \equiv (a+b)\; \text{mod}\; n$

I'm currently self-studying a course in cryptography, and i understand the importance of understanding modular arithmetic fully. I have proved many operations on modular arithmetic, but one i am stuck ...
1
vote
2answers
23 views

Show that if $\gcd(a,pq)=1$ and $g=\gcd (p-1, q-1)$ then $a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$.

Suppose $p\neq q$ are two primes and $g=\gcd (p-1, q-1)$ Show that if $\gcd(a,pq)=1$, then $$a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$$ Hi, how to do? I have no idea how to begin, Thanks.
3
votes
1answer
176 views

Show that $3x^2 - 7y^2 = 1$ has no integer solutions

Show that $3x^2 - 7y^2 = 1$ has no integer solutions A bit confused with this problem, my professor gave me a hint saying that I would need to use a "good mod" although I am not sure how to go about ...
0
votes
1answer
34 views

Let $p$ be and odd prime. Use Wilson's Theorem to show that…

Let $p$ be and odd prime. Use Wilson's Theorem to show that: $[(\frac{p -1}{2}) !]^2$ $\equiv$ $(-1)^{(p+1)/2}$ mod $p$ My understanding is that this should be as simple as picking an odd prime and ...
0
votes
2answers
38 views

Evaluate $2488^{2016}\equiv ?\pmod 7$ [closed]

Evaluate $2488^{2016}\equiv ?\pmod 7$. How do I solve these kind of questions ? Is that modular exponentiation or modular arithmetic ?
0
votes
0answers
23 views

Twin Prime Max Gaps

Ok, let's build a foundation here: A common way of testing primality, is dividing by all primes smaller than the number's square root. For instance, $97$ is prime because dividing by none of the ...
-1
votes
4answers
48 views

Prove that: $2^{n} \equiv 1 \pmod {9} \implies 2^{n} \equiv 1 \pmod {7}$

Prove that: $$2^{n} \equiv 1 \pmod {9} \implies 2^{n} \equiv 1 \pmod {7}$$ Please a hint and a help
0
votes
2answers
36 views

Prove that : $10^{5n+2}+(-1)^{n}\cdot 4 \equiv 0 \pmod {13}$

Prove that : $$10^{5n+2}+(-1)^{n}\cdot 4 \equiv 0 \pmod {13}$$ I don't have enough skills in modular to do it Please help
0
votes
2answers
38 views

Primitive 8th roots of unity in Z17

If $\omega=\frac{\sqrt{2}}{2}+i \frac{\sqrt{2}}{2}$, then $\omega$ is an 8th root of unity. And I know $\omega,\omega^3,\omega^5$,and $\omega^7$ are furthermore primitive 8th roots of unity in ...
2
votes
1answer
77 views

Prove that a perfect square (also a perfect square backwards) is divisible by 121

Suppose that $n=x^2$ is a perfect square with an even number of base-10 digits. Assume that when n is written backwards, you get another perfect square $y^2$. Prove that 121|n. (Use the mod 11 ...
-1
votes
1answer
61 views

Square Root of $5$ mod $10^{9}+7$ [closed]

$My$ $Current$ $Knowledge:$ We can find it if 5 is a $Quadratic$ $residue$ modulo p and where p is prime and we can check it using $Euler$ $criterion$. I cannot able to find the root(5)mod 1000000007. ...
0
votes
0answers
23 views

Modular residue number theory problem.

Given large enough integer $N$ is there always $(\lceil\log N\rceil)^d$ pairs of integers $z,p$ where each of $p$ is distinct prime with $N<p$ and $z$ satisfies $z\bmod p<\frac{zN\bmod p}{N}$ ...
4
votes
1answer
24 views

Defining a homomorphism given a mapping and terminology/notation associated?

So the problem is: "Define a homomorphism $f: (\mathbb{Z}_6, +_6) \ \xrightarrow{onto} (\mathbb{Z}_3, +_3)$. Explicitly tell me how f is defined: Show f is a function, show f is a homomorphism. " ...
1
vote
2answers
18 views

Finding Inverse in modulus m

I've been learning the Euclidean algorithm and came across this simple problem. $101^{-1} (mod 203)$ So I attempted it as such: $203 = 101(2) + 1$ So we got a gcd of 1, we can stop and do: $1 = ...
0
votes
1answer
43 views

Find the inverses of 2,3,…,16 modulo 17. [closed]

I need to find the inverses of 2,3,...,16 modulo 17 and use to solve (a) 5x ≡ 9 (mod 17); (b) 11x ≡ 3 (mod 17). I found the inverse of 5 modulo 17, to be 7 modulo 17 and know to solve by multiplying ...
0
votes
0answers
16 views

Modular arithmetic involving real numbers

For some $M \in \mathbb{N}$, let $a,b,r,s \in [0, M)$. Compute the following: $$ x = (a+r) \mod M$$ $$ y = (b+s) \mod M$$ $$ z = (x \cdot y) \mod M = (a \cdot b + a \cdot s + b \cdot r + r \cdot s) ...
0
votes
1answer
45 views

Last digit of a number

I was currently solving a question of permutations and in that I had to find the total ways of something. The answer was ${8\choose 4}$ which has last digit $0$ . A random thought that came to my ...
3
votes
1answer
81 views

Closed form for Fibonacci numbers

We know the closed form for Fibonacci number as $F_n=\frac{1}{\sqrt5}\left[\left(1+\frac{\sqrt5}{2}\right)^n−\left(1−\frac{\sqrt5}{2}\right)^n\right]$ But while finding $F_n \pmod{99991}$ the closed ...
0
votes
1answer
120 views

Multiply $3$ or more numbers at the same time.

Consider a set of numbers $N \in \Bbb N $ in the range $[1, M[$, where all the numbers are co-prime with $M$ How can we easily multiply certain numbers of that set at the same time, where computation ...
0
votes
1answer
50 views

Find all seventh-power residues modulo $29$. [duplicate]

Find all seventh-power residues modulo $29$. I have an indices table to refer to in the back of my book but have to solve this by hand. I am under the assumption this involves Fermat's Little ...
1
vote
3answers
66 views

Find all solutions to $x^9 \equiv 25$(mod 29)

Find all solutions to $x^9 \equiv 25$(mod 29) I referred to a table of indices in the back of my book for help but am still a bit confused, any help/hints are greatly appreciated.
2
votes
1answer
22 views

Use the generalization of Euler's criterion to determine if 16 is a cubic residue modulo 31…

Use the generalization of Euler's criterion to determine if $16$ is a cubic residue modulo $31$. So far I have: $p = 31$, $m = 3$, $d = (p-1, m) = (30,3) = 3$ if $16^{30/3}= 16^{10}= 1 \pmod{31}$ ...
2
votes
1answer
54 views

Any method to solve this system of equation?

We have m variables $ x_{1},x_{2},...,x_{m} $ which are elements of field $F_{p}$ and we are given m equations of the form $$\sum_{i=1}^{m} x_{i}^{n} = c_{n} \mod p \qquad for \: 1 \le n \le m$$ ...
8
votes
1answer
169 views

How to compute the Hecke operator on an Eisenstein series?

In my current course on Modular Forms we are now discussing Hecke operators and we are asked the following: Prove that for any even integer $k \geq 4$ and prime $p$ we have $T_pG_k = ...
5
votes
2answers
61 views

Prove that ${ ({ 3299 }^{ 5 }+6) }^{ 18 }\equiv 1\pmod{112}$

How do I solve this? Prove that ${ ({ 3299 }^{ 5 }+6) }^{ 18 }\equiv 1\pmod{112}$ Also, it would be very helpful if you could give me something to read on the topic since this is not taught at ...
2
votes
0answers
96 views

Find polynomial congruent to function modulo 6

How to find polynomial with rational coefficients, which is congruent to given function (or prove that it doesn't exist)? Particularly, how to find $P(x)$, so $$P(x)\equiv ...
2
votes
2answers
40 views

In which situations $\det(A\mod x) \mod x=\det(A)\mod x$ would help us knowing if $\det(A)=0$?

André Nicolas, in his very neat answer to is the following matrix invertible? uses the fact that the matrix $$ \begin{bmatrix} 1235 &2344 &1234 &1990\\ 2124 & 4123& 1990& 3026 ...
0
votes
0answers
41 views

Given an integer x^3 ≡ n (mod p), can we find x?

Okay, I have this for a class homework question. If we are given n and p, I know a few things: If p≡1 (mod 3), then we can use the theorem of cubic reciprocity to determine whether there exists an ...
0
votes
0answers
18 views

Prove that the product of the primitive roots modulo the prime p is congruent to 1 modulo p if p > 3? [duplicate]

Prove that the product of the primitive roots modulo the prime p is congruent to 1 modulo p if p > 3. Just started going over primitive roots in class and a bit lost with this question. I do know ...
0
votes
1answer
23 views

Find the Ф(28) = 12 primitive roots modulo 29…

Find the Ф(28) = 12 primitive roots modulo 29... Only had a very brief introduction to primitive roots and a bit lost with this problem. Based on my limited understanding so far I have: Ф(28) = 12 ...
0
votes
2answers
44 views

For which positive exponents $e$ is $2^e \equiv 1\pmod{17}$? [closed]

For which positive exponents $e$ is $2^e \equiv 1\pmod{17}$? We are currently covering a section on primitive roots, indices and power residues. I am really lost with this one, any hint/help is ...
0
votes
1answer
15 views

Proof for remainder operator on subtraction

Given a>b, a>0,b>0,p>0, and % being the remainder operator For finding (a-b)%p, I ran some random cases in python terminal and came up with following, however I am facing difficulty proving it. ...
3
votes
0answers
31 views

Recreational math dealing with twin primes

This is kinda recreational math with a goal in mind of progressing further toward a proof of the twin prime conjecture. Consider this: We start with a random prime: $109$ $3*109=327$ $327 ...
1
vote
1answer
30 views

Modulo multiplicative inverse of floating numbers

I have a floating value $k$ and an integer $P$ I want to calculate $(\dfrac{k}{\sqrt5}) \mod P$ How do I calculate it? PS: I know how to calculate MMI (Modulo Multiplicative Inverse of integer ...
1
vote
1answer
45 views

Sets of coprime order (m,n) have period of (m • n), but why?

I'm trying to understand the mathematical principles behind an algorithm I've created. I'll explain how it works practically: The algorithm takes an integer as input and returns a string. In the ...
0
votes
1answer
44 views

Let p be a prime and k a positive integer such that $a^k$mod p = a mod p for all integers a. Prove that p - 1 divides k - 1.

Let p be a prime and k a positive integer such that $a^k$mod p = a mod p for all integers a. Prove that p - 1 divides k - 1. I think I need to use Fermat's Little Theorem, and I can get ...
1
vote
4answers
58 views

How to solve the congruence $y^{31}\equiv 3 \mod{100}$

$\phi (100) = 40$ Hence: $y^{31}\equiv y^{-9} \equiv 3\mod{100}$ $y^{9}\equiv 67 \mod{100}$ However I do not know where to go from here.
0
votes
1answer
39 views

How would I find the modulo of a large number without using a calculator that supports large numbers?

How would I find the modulo of a large number without using a calculator that supports large numbers like wolfram alpha. EX: $113^{17} \pmod{91}$
0
votes
0answers
11 views

Modular exponentiations with two moduli?

Can someone explain the following modular exponentiation statement step by step? The statement is: Suppose $p,q$ are primes and $q~|~p-1$, $k\in \mathbb{Z}_q$ and $k^{-1}$ is computed mod $q$. Then, ...
0
votes
1answer
26 views

Simplifying Large Bases with large Exponents

I'm told to find: $105 308^{7125} \pmod {11}$ I'm not exactly sure how to go about calculating this. I know that I could split the exponent into multiples of it, for instance. $7125 = 7 * 10 * 10 * ...
0
votes
0answers
36 views

If $p=x^2+y^2$ is a prime number, then $\left( \frac{x+y}{p} \right) = \left( \frac{2}{x+y} \right) $

Let $p=x^2+y^2$ be a prime number. How to prove that $\left( \dfrac{x+y}{p} \right) = \left( \dfrac{2}{x+y} \right) $ (where $\left(\frac ab\right)$ denotes the Jacobi symbol)?