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

8
votes
1answer
167 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
60 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
69 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
37 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
17 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
21 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
43 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
13 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
28 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
28 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
43 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
38 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
56 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
37 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)?
4
votes
3answers
74 views

Last Digit of $x^0 + x^1 + x^2 + \cdots + x^{p-1} + x^p$

Given $x$ and $p$. Find the last digit of $x^0 + x^1 + x^2 + \cdots + x^{p-1} + x^p$ I need a general formula. I can find that the sum is equal to $\dfrac{x^{p+1}-1}{x-1}$ But how to find the ...
2
votes
2answers
23 views

Product of three primitive roots mod prime number

Let $p$ be a prime number, and let $a,b,c$ be primitive roots mod $p$ (repetitions allowed). Is it true, in general, that $a\cdot b\cdot c$ is a primitive root? I have proved that $ab$ cannot be a ...
0
votes
0answers
15 views

Doubt regarding quadratic sieve

Is calculating $a^2 \equiv p-5 \pmod{p} $ same as calculating $a^2 \equiv 5 \pmod{p} $ ?My code (using quadratic residue method) returns same answers corresponding to both the equations for any odd ...
0
votes
2answers
55 views

How to solve this modular equation

I am not able to solve this Equation : $$x^2 \equiv 5 \pmod{10^9+7}$$ $x$ is a positive integer. What is the general approach to do this ?
1
vote
1answer
27 views

If $a^{p-1} \equiv 1 \pmod p$ and then $a^{\frac{p-1}{2} } \equiv 1$ or $p-1 \pmod p$?

today I have some question to ask you about modular arithmetic that I'm stuck to this. If $a^{p-1} \equiv 1 \pmod p$ then $a^{\frac{p-1}{2} } \equiv 1$ or $p-1 \pmod p$ is true or not ? If ...
9
votes
1answer
535 views

2016 Spain Math Olympiad final stage, problem 2

Given a prime $p$. Prove that there exist $\alpha$ such that $p|\alpha(\alpha-1)+3$, if and only if there exist $\beta$ such that $p|\beta(\beta-1)+25$. My solution: Using quadratic residuu we ...
2
votes
1answer
122 views

Calculating Irrationals raised to some Power modulo 1000000007 [closed]

Lets define a function F as $F(n) = 1+(\frac{1+{\sqrt 5}}{2})^n$ As per wolfram site, ${\sqrt 5}\%99991=10104$ As per wolfram site, ${\sqrt 5}\%1000000007=no\_solution$ I need to find the value of ...
-1
votes
0answers
28 views

Divisibility Digit Product, Number Theory Problem

Find the least positive integer n satisfying the following properties: n is divisible by 3 but not 9, and the sum of,n and the product of the digits of n is divisible by 9. What is a simple way of ...
0
votes
2answers
72 views

Reverse of Chinese Remainder Theorem

For the following: $(102n-51) \not\equiv 2 \pmod {2,3,5,7,11,13,...,\sqrt{102n-51}}$ (That's probably completely incorrect use of symbols, but I mean not equivalent to 2 mod any prime less than ...
1
vote
0answers
37 views

Primitive roots generated from a primitive root

Let $p$ be a prime number, and let $a$ be a primitive root $\mod p$. Is it true that $a^m$ is a primitive root if and only if $\gcd(m,p-1)=1$? One direction is correct: if $a^m$ is a primitive root, ...
0
votes
2answers
49 views

Finding ALL solutions of the modular arithmetic equation $25x \equiv 10 \pmod{40}$

I am unsure how to solve the following problem. I was able to find similar questions, but had trouble understanding them since they did not show full solutions. The question: Find ALL solutions ...
0
votes
4answers
33 views

$x = x' \pmod N$ iff $N$ divides $x - x'$

This is one of the first lines in one of my lecture notes, where they write: $x = x' \pmod N$ if and only if $N$ divides $x - x'$ I've taken a discrete maths course a while ago but this doesn't ...
0
votes
3answers
68 views

How to prove the following modulo equation

Let $$ p=a^{2}+64b^{2},\:a,b\in\mathbb{Z}$$ is a prime number. Prove that $$ 2^{(p^{2}-1)/4}\equiv1\:\left(mod\:p\right)$$
0
votes
3answers
56 views

Does a mod p mod q = a mod q mod p?

How to prove/disprove that (a mod p) mod q = (a mod q)mod p ? Supposing $p < q$, we have 3 situations: $a{\space}{\epsilon}{\space}[0, p)$, obviously the statement is true for this case ...
1
vote
1answer
20 views

Divisbility and Sum of Nth Powers

Let $S = 1^N + 2^N + \dots + N^N$. Show that $S \ \text{mod} \ N = 0$ for any odd $N$. What would be a good way to start this problem?
1
vote
0answers
20 views

Determine the quadratic character of 293 mod 379…

Determine the quadratic character of 293 mod 379. Did several other problems like this with 3, 5, 60, -1 and 307 all mod 379 but still having a tough time with this problem. I can post up work from ...
1
vote
2answers
29 views

Is the modulus of an exponent always $\phi(n)$ in a modulo $n$ expression?

According to this proof, given an expression $$x^e\pmod n$$ the modulus of the exponent $e$ is $\phi(n)$. From Euler's Theorem, I know that $$x^{\phi(n)}\equiv 1\pmod n$$ holds true iff $x$ is ...
0
votes
1answer
45 views

polynomials modulo even numbers

Say I have $R= \mathbb{Z}[x]$ and $A = \{p_0+p_1x+p_2x^2+\cdots+p_nx^n \mid n\geqslant0, p_i\in\mathbb{Z}, p_0, p_1 \text{ even}\}$. Define $K=R/A$. How would I characterize the elements of $K$? ...
1
vote
1answer
21 views

proving: ∀𝑎, 𝑏 ∈ ℤ, $2(𝑎 + 𝑏)^8 ≡_4 2(𝑎^8 + 𝑏^8)$

For this question, my way of proving it is: write: $4|(2(\binom80a^8 + \binom81a^7b + \binom82a^6b^2... \binom88b^8) - (2a^8 +2b^8)$ since $2a^8 \ and\ \ 2b^8$ are eliminated, I just need to write ...
0
votes
0answers
25 views

Solving congruence relation with non-prime numbers

I've been working on some homework, and have gotten stuck on the question. Find ALL the solutions (between 1 & 40) to the equation $ 25x \equiv 10 \pmod {40}$ Apologies, I'm new, and not ...
0
votes
1answer
28 views

Evaluate $\left(\frac{3}{11}\right)$ using Euler's Criterion…

Evaluate $\left(\frac{3}{11}\right)$ using Euler's Criterion. So far I have: $$\left(\frac{a}{p}\right) =a^{\frac{p-1}{2}}\implies \left(\frac{3}{11}\right)=3^{\frac{11-1}{2}}=3^5$$ I am a bit lost ...
2
votes
1answer
16 views

Determine the quadratic character of the given numbers modulo the prime 379.

a.) -1 b.) 307 I solved the same problem for 3, 5 and 60 but am having a tough time with these remaining two. Help with either one is greatly appreciated.
0
votes
0answers
42 views

finite field arithemtic

I have the following question. Let $A_1, A_2$ be elements in $F_{2^n}$. Let $M$ be an $n$ x $n$ matrix with elements in $Z_2$. I am looking for two $n$ x $n$ matrices $M_1$ and $M_2$ over $Z_2$ such ...
1
vote
1answer
21 views

Solving for the base of a modular exponent for El Gamal cryptosystem

We are given $B \equiv g^b \mod p$ and the values for $B,b,p$ but not $g$. How can we determine $g$ from the knowledge of $p, b$ and $B$, provided that $\gcd(b, p − 1) = 1$. The only solution that ...
0
votes
0answers
37 views

Calculate $(\frac{3}{11})$ in the following ways…

Evaluate $(\frac{3}{11})$ Currently going through a study set on a Quadratic Reciprocity, I have to evaluate $(\frac{3}{11})$ in the following three ways: (1) Computing the squares modulo 11 (2) ...
1
vote
3answers
54 views

Find the remainder of $9^2\cdot 13\cdot 21^2$ when divided by $4$

Find the remainder of $9^2\cdot 13\cdot 21^2$ when divided by $4$ How should I approach this type of questions? Without calculator of course I did this: $9^2\cdot 13\cdot 21^2=81\cdot 13\cdot ...
0
votes
2answers
22 views

How to show that there are just $n$ cosets for the $n\mathbb{Z}$ relation?

Consider $n\in \mathbb{Z}$ with $n > 0$, we define $n\mathbb{Z}=\{kn \in \mathbb{Z} : k\in \mathbb{Z}\}$. It is easy to see that $n\mathbb{Z}$ is a normal subgroup of the additive group ...
3
votes
1answer
237 views

Broken Clock vs Normal Clock

I'm trying to prepare for an interview and have looked at this problem: There's a broken clock and a normal clock. The broken clock moves "rate" seconds each second, while the normal clock moves a ...
0
votes
2answers
57 views

Can we define 4/8 = 8 mod 10?

This question came to mind when I saw another question involving modular-arithmetic division. In $\mathbb{Z}/10\mathbb{Z}$ we can divide 4 by 7 by identifying 3 as a multiplicative inverse of 7 and ...
1
vote
1answer
44 views

Find smallest x so that 13^k ≡ x (mod 100)

Let $a_1 = 13$ and for n ≥ 2, let $a_n = 13^{a_{n−1}}$. What is the smallest positive integer x so that $a_{1834} ≡ x$ (mod 100)? I know that by Fermat's little theorem, $a_{1834} ≡ 13$ (mod 13), ...
0
votes
1answer
103 views

Given $m$, $n$, and $x$ is it possible to know whether there exists a $c$ and $i$ such that $m^ci \equiv x\pmod{mn - 1}$

The full problem is as follows; Given $m, n, x$; $\\m, n, x \in \mathbb{Z^+}$ $\\1 \lt m, n$ $\\1 \lt x \lt mn - 1$ can we know that whether there exists a $c$ and $i$ satisfying $\\i, c \in ...
2
votes
2answers
48 views

Show that $17$ divides $p-1$

I'm given that $s=2^{17}-1$ and that $p$ is a prime factor of $s$. First I'm asked to show that $2^{17}\equiv 1(\mod p).$ For this I have simply said that since $p$ divides $s$, this means that ...