We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [modular-arithmetic]

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 $a-b$.

Filter by
Sorted by
Tagged with
0
votes
0answers
19 views

Modular arithmetic with symbolic variables in MATLAB

How can I use modular arithmetic on a matrix that has symbolic variables? I want the coefficients of polynomials in t and 1/t to be mod 2. syms t mod( [t^2-1/t-t,-1/t^2;t^2,0],2) gives me FAIL. ...
1
vote
4answers
62 views

Finding all integers $k \geq 2$ such that $k^2 \equiv 5k \pmod{15}$. What is going on here?

The question is as follows: Find all integers $k \geq 2$ such that $k^2 \equiv 5k \pmod{15}$. I have an issue related to this question (its not about the solution to the question): I know that $\...
1
vote
2answers
49 views

Does the set $H=\{1,4,7,13\}$ with modulo $15$ multiplication, $\otimes_{15}$, create a group?

Does the set $H=\{1,4,7,13\}$ with modulo $15$ multiplication, $\otimes_{15}$, create a group? $$\begin{array}{|r|c|c|c|} \hline \otimes_{15} & 1 & 4 & 7 & 13\\ \hline 1 & 1 &...
0
votes
1answer
37 views

Modulo division: Find all integers $k \geq 2$ such that $k^2 = 5k(\mod 15).$ [duplicate]

Find all integers $k \geq 2$ such that $k^2 = 5k(\mod 15).$ Using arithmetic on $\mathbb{Z}_{15},$ $\bar{k}^2 = \bar{5}\bar{k},$ may I divide both sides by $\bar{k}$ to arrive at $\bar{k} = \bar{5}?$
1
vote
0answers
42 views

What is the inverse of this Frobenius endomorphism?

Let $p$ be a prime. The Frobenius map: $x \mapsto x^3$ is bijective from $\mathbb{F}_p \longrightarrow \mathbb{F}_p$. I'm trying to write its inverse map: $x \mapsto x^{?}$. I suppose the ($?$) must ...
2
votes
1answer
56 views

Show that $2^q\equiv 1$ mod p

Let $p=2q+1$ and $q$ be prime numbers, with $q\equiv 3\:(4)$. Show that $2^q\equiv 1\:(p)$. So far I've tried to write $q$ as an expression of $p$ and I am assuming that I have to use little Fermat ...
0
votes
6answers
92 views

Can I prove this using modular congruence? $3 \mid 5^n + 2\cdot11^n$ [EDIT] [closed]

I'd prove this by induction, and I'd been thinking in how prove that using congruence. Please help. [EDIT] I can got to in (−1)^n+(−1)^n+1 mod 3, but I don't know if this it's a congruent mod 3 ...
1
vote
2answers
58 views

Showing $x^4+x^3+2x+15$ is irreducible in $\mathbb{Q}[x]$

Specifically, I'm trying to solve this problem: Prove that $p(x)=x^4+x^3+2x+15$ is an irreducible polynomial in $\mathbb{Q}[x]$ by considering $p(x)$ mod $3$ and showing that $p(x)$ has no rational ...
1
vote
3answers
47 views

Prove that if $[a]_n = [r]_n$, then $[a^k]_n = [r^k]_n$

Let $a, r, n \in \mathbb{Z}$ with $n>0$. Prove that if $[a]_n = [r]_n$, then for all $k \in \mathbb{N}$, $[a^k]_n = [r^k]_n$. So far this is what I have: Proof: Let $a, r, n \in \mathbb{Z}$ with $...
-2
votes
1answer
20 views

Given that $7x^2 - 40xy + 7y^2 = (|(x - y)| + 2)^3$ And $x-y\equiv a(\mod 13)$ Solve for $a$ [closed]

Given that $$7x^2 - 40xy + 7y^2 = (|(x - y)| + 2)^3$$ and $x-y\equiv a(\mod 13)$. Solve for $a$ Im not sure how to approach this, hints and solutions would be appreciated.
2
votes
1answer
51 views

Find the smallest positive integer which can be expressed as the sum of four positive squares and divides $2^n +15$

Find the smallest positive integer which can be expressed as the sum of four positive squares, not necessarily different, and divides $2^n + 15$ for some positive integer $n$. If you let $K$ be that ...
0
votes
1answer
48 views

Solving a congruence with a variable remainder

Using a MS Excel spreadsheet, was conjecturing the following scenario, of a congruence such that: $ 7+3*x\equiv2*x+5\pmod{42}$ Where a solution is: $\quad x = 6$ In 'rebalancing' the congruent ...
0
votes
1answer
33 views

Find prime fields over which a polynomial has roots.

Suppose we have a polynomial $$h(x) = a_n x^n + \dots + a_1 x + 1$$ Given the values $a_1,\ldots,a_n$, how to determine whether there exists such prime $p$ that $h(x)$ has roots over the field $\...
5
votes
1answer
157 views

How many natural number between $100$ and $1000$ exist which can be expressed as sum of 10 different primes.

How many natural number between $100$ and $1000$ exist which can be expressed as sum of 10 different primes. For example , we can write $129$ as : $$129 = 2+3+5+7+11+13+17+19+23+29$$ What would be ...
0
votes
1answer
55 views

Preimages of elements in linear maps involving finite fields

I'm reading a text for one of my classes, and I came across this theorem: Theorem 4. Suppose $V$ is an $m$-dimensional vector space over $\mathbb F_p$. Suppose $T : V → W$ is a linear map. Write $n$...
1
vote
0answers
31 views

Cardinality Of Set Where No Sum Of Elements Equals Some $k$

What is the greatest cardinality of a set $S$ of positive integers strictly less than $k$ such that no subset of $S$ sums to $k$, in terms of $k$? I worked this out for small values of $k$, and ...
1
vote
1answer
91 views

Elementary Number Theory and Congruences

Let $f(x) = x^m + a_1x^{m−1} + · · · + a_{m−1}x + a_m$, with $a_j \in \mathbb{Z}$, be a polynomial with integer coefficients and $m \geq 1$. (i) Show that if $a$ and $b$ are integers with $a \equiv b ...
1
vote
3answers
36 views

Proving isomorphism on additive group $(\Bbb{Z}_4,+)$ and multiplicative group $(\Bbb{Z}_5^*, \times)$

The question I'm having problems with involves proving the above groups are isometric. Therefore, I have to prove they are bijective (1-1, and onto) and homomorphic. I have done the group operations ...
4
votes
1answer
56 views

Proof writing: looking for help in precisely expressing an idea I have about combinations of pairs of distinct residue classes

I am working on an idea which I would call "pairs of distinct residue classes for a given set of distinct primes" which is an attempt to count the number of possible combinations of residue classes in ...
1
vote
1answer
89 views

Multiplicative Inverse of $19 \pmod{26}$ [closed]

This is the work I have tried somehow I keep getting 4 instead of 11: $26 = 1\times 19 + 6$ $19 = 3\times 6 + 1$ Now, $1= 19 - 3\times 6$ Sub $6 = 26 - 19$ $1 = 19 -3(26-19)$ $1 = -3\times 26 + ...
2
votes
1answer
90 views

Find all five digit number $\overline{abcde}$ such that $\overline{abcde} = \overline{(ace})^2$

Find all five digit number $\overline{abcde}$ such that $$\overline{abcde} = \overline{(ace})^2$$ This question popped in my mind while solving other elementary numbers and I have been trying to ...
1
vote
0answers
39 views

Proof using modulo

Suppose $n|m$, then $n\cdot d=m,~d\in\Bbb Z$. If $a\equiv b\mod m$, then $a\equiv b\mod{n\cdot d}$. Additionally, $d\equiv d\mod{n\cdot d}$. So we know $ad\equiv bd\mod{n\cdot d}$. ...
3
votes
2answers
63 views

Is there a standard group presentation for the group of units $U(n)$ modulo $n$?

According to Approach0, this is a new question to MSE. The Details: Definition: The group $U(n)$ of units modulo $n$ is the group under multiplication modulo $n$ of all equivalence classes $[a]_n$ ...
-2
votes
3answers
54 views

If a is a $\mathbb Z / p\mathbb Z$ generator, if $k$ is not a multiple of $p-1$, $a ^ k \not\equiv 1\pmod p$ [duplicate]

If $a$ is a $\mathbb Z / p\mathbb Z$ generator, if $k$ is not a multiple of $p-1$, $a ^ k \not\equiv 1\pmod p$. I don't understand why. What does "$a$ is a $\mathbb Z / p\mathbb Z$ generator" mean? ...
1
vote
0answers
48 views

Prob. 15, Sec. 1.3, in Herstein's TOPICS IN ALGEBRA 2nd ed: If $(m, n)=1$, then, given $a$ and $b$, there is an $x$ such that

Here is Prob. 15, Sec. 3, in the book Topics in Algebra by I.N. Herstein, 2nd edition: If $(m, n) = 1$, given $a$ and $b$, prove that there exists an $x$ such that $x \equiv a \mod m$ and $x \equiv ...
0
votes
1answer
66 views

Are there positive integral solutions for this simple system?

What are solutions (if any) of the following system for $n_i,m_i \in \mathbb{Z}_{\ge 0}$ and $i=1,2$ ? $$\left\{ \begin{array}{ll} m_1n_2 + m_2n_1 = n_1n_2 \\ n_i^2 \ge 1+m_jn_j \text{ for } i \neq ...
2
votes
4answers
91 views

Solving the congruence $7x + 3 = 1 \mod 31$?

I am having a problem when the LHS has an addition function; if the question is just a multiple of $x$ it's fine. But when I have questions like $3x+3$ or $4x+7$, I don't seem to get the right answer ...
0
votes
0answers
37 views

Show that $4((n-1)!+1)+n$ is divisible by $n(n+2)$ [duplicate]

I have to prove the following statement: If $n$ and $n+2$ are prime numbers, then $4((n-1)!+1)+n$ is divisible by $n(n+2)$. My approach is to show that $4((n-1)!+1)+n$ is divisible by $n$ and by $n+...
0
votes
2answers
33 views

Groups with the subtraction operation

Why do integer mod integer sets with the operation of subtraction not form groups? For example, integers mod 3 is {0,1,2}, which has an identity (0) and inverses (self inverses). And subtraction is ...
2
votes
1answer
33 views

Checking a result obtained by Chinese Remainder Theorem

I have the following two linear congruences: $$x \equiv 3 + n\mod p_1 $$ $$x \equiv 3 - n\mod p_2$$ where $p_1$ and $p_2$ are distinct primes, and $n$ is the difference between those primes. Does ...
1
vote
1answer
59 views

Use Wilson's Theorem to show $(q!)^2+(-1)^q \equiv 0$ mod p

Let $q=\frac{p-1}{2}$ and $p$ is an odd prime. Show that $$(q!)^2+(-1)^q\equiv 0\:\:\text{mod p}$$ After searching for a while, I couldn't find this specific congurence question. So therefore I am ...
1
vote
0answers
31 views

about a fundamental domain and its volume

Let $a, b, c$, pairwise coprime squarefree integers. Suppose $au^2 + bv^2 + cw^2 ≡ 0 (mod\ 4)$ with $au^2 , bv^2 , cw^2$ pairwise coprime and $(u, v, w) ⊂ \Bbb Z^3$ Let $Λ_0 := \{(x, y, z) ⊂ \Bbb Z^...
1
vote
3answers
69 views

Help with finding solutions to $x^3\equiv 1 \pmod{61}$ etc.

"How many incongruent solutions does $x^3 \equiv 1$ have modulo 59? What about for mod 61? Now consider, $x^3 \equiv 8 \mod 59$ and $\mod61$? How about the congruences $y^5 \equiv 1$ and $y^5 \...
1
vote
2answers
45 views

Find a $k$ such that $3^k \equiv -6 \pmod{43}$

I have been trying to find this $k$, but I am stuck. The only information I could extract was from the Fermat's Little Theorem: Since $43$ doesn't divide 3 and it is a prime, it follows $3^{42} \...
1
vote
1answer
24 views

quadratic equation modulo product of coprime squarefree integers

Let $a, b, c$, pairwise coprime squarefree integers. Suppose $au^2 + bv^2 + cw^2 ≡ 0 (mod\ |abc|)$ with $au^2 , bv^2 , cw^2$ pairwise coprime. Prove that if $(x,y,z) \in Λ_0 := \{(x, y, z) ⊂ \Bbb Z^...
1
vote
2answers
39 views

Proof that if $\gcd(a,n) = 1$, then $a^k \equiv a^{k \pmod{\phi(n)}} \pmod n$

From Euler's theorem I know that $a^{\phi(n)} \equiv 1 \pmod n$ if $\gcd(a,n) = 1$. However I can't find any proof/explaination of the proof in the title.
-1
votes
3answers
67 views

What are the elements of the modular ring mod 7?

Just getting started with modular arithmetic. Are the elements of a modular ring simply the set of all the numbers from $1$ to $p-1$? in this case $p-1 = 6$ ?
8
votes
2answers
220 views

A hard question in number theory

Prove that for every natural number $n$, there is a set $S$ of $n$ natural numbers such that for any two different numbers $a,b$ From $S$ the number $a-b$ divides $a$ and $b$ and no another number ...
1
vote
1answer
83 views

Given two primes $p$, $q$ and their product $pq$, find $\phi(pq)$ mod $p + q$

This is actually from a past year exam question for a computer security module, which I am doing to prepare for my upcoming test. The question provides $pq = 1669806207577$ (for ease of reference, I ...
4
votes
0answers
89 views

Counting primes in residue classes

Suppose you are sorting all of the prime numbers between $1$ and some large number $N$, from smallest to largest; into buckets which correspond to their residue classes modulo some prime $p_i$. Now ...
1
vote
4answers
68 views

Proof that $3^{10^n}\equiv 1\pmod{10^n},\, n\ge 2$

This should be rather straightforward, but the goal is to prove that $$3^{10^n}\equiv 1\pmod{10^n},\, n\ge 2.$$ A possibility is to use $$\begin{align*}3^{10^{n+1}}-1&=\left(3^{10^n}-1\right)\left(...
3
votes
6answers
82 views

Prove that $2x^3+3x^2+x$ is always divisible by 6 if x is an integer. [duplicate]

Prove that $2x^3+3x^2+x$ is always divisible by $6$ if $x$ is an integer. I started by factoring the expression: $x(2x^2+3x+1)=x(2x+1)(x+1)$ However I wasn’t sure how to progress from here to prove ...
0
votes
0answers
20 views

Determine a criterion for divisibility by $7$, and uuse it to determine the reminder of the number $12345678923$ when divided by $7$ [duplicate]

I am not sure how i would start this. It would be something mod $7$ but i don't know where to go from there
1
vote
3answers
46 views

Given integers $m$ and $1 \lt a \lt m$, with $a \vert m$, prove that the equation $ax\equiv 1\pmod{m}$ has no solution.

Given integers $m$ and $1 \lt a \lt m$, with $a \vert m$, prove that the equation $ax\equiv 1\pmod{m}$ has no solution. (That is, if $m$ is composite, and $a$ is a factor of $m$ then $a$ has no ...
2
votes
0answers
34 views

Stuck on Consecutive Moduli Selection (Residue Number System)

I'm preparing for my final year project in school and i plan on working on the implementation of Residue Number System in Image Processing. I found this thesis online by Pallab Maji here: http://...
7
votes
1answer
216 views

For what values of n is $2^{2n} -1$ divisible by $4n+1$

For what values of n will the expresion $2^{2n} -1$ be divisible by $4n+1$. I have checked using a computer and the values of 2n I get are 8,20,36,44,48,56,68,96,116,120,128,140,156,168,170,176 $\...
0
votes
2answers
73 views

For any integers $a$ and $b$, $ab = 0$ implies $a = 0$ or $b = 0$. Prove that this remains true mod prime numbers but not true mod a composite number.

I roughly understand modular arithmetic but I am having trouble starting the problem. I can prove it for just integers but I can't seem to relate it to mod primes and composites?
1
vote
2answers
68 views

Modular-arithmetic proofs

Read examples $3.2.2$ and $3.2.3$ and answer the following questions: Example $3.2.2.$ Find a solution to the congruence $5x\equiv11\mod 19$ Solution. If there is a solution then, by Theorem ...
0
votes
2answers
24 views

In $\Bbb{Z}/m\Bbb{Z}$, show that $([a]_m)^{qd+r} = (([a]_m)^d)^q([a]_m)^r$

In $\Bbb{Z}/m\Bbb{Z}$, show that $([a]_m)^{qd+r} = (([a]_m)^d)^q([a]_m)^r$. My first attempt at this question was to use simple arithmetic properties to prove this true, however, this is incorrect. ...
1
vote
1answer
65 views

Determine remainders of large numbers

a) Determine a criterion for divisibility by 7, and use it to determine the remainder of the number $12345678923$ when divided by 7. b) Assume $a≡b(\mod m)$. If $r≡s(\mod m)$ is it true that $ar≡...