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
1 vote
0 answers
47 views

Homomorphism between $\mathbb{Z}/m$ and $\mathbb{Z}/n$

The lecture notes I am working through assert, but leave as an exercise, that if $n\mid m$, then the map $f:\mathbb{Z}/m\to \mathbb{Z}/n$ sending$$x\mapsto x\pmod n$$is a surjective homomorphism. My ...
user avatar
1 vote
1 answer
34 views

Using modular arithmetic to prove that $5 \mid x^6-x^2$ for any integer $x$. [duplicate]

Problem: Using modular arithmetic to prove that $5 \mid x^6-x^2$ for any integer $x$. By Fermat's Little theorem we have $$x^5 \equiv x \mod 5.$$ Hence $$x^6 - x^2 \equiv x \cdot x - x^2 \equiv 0 \...
user avatar
  • 11.9k
1 vote
0 answers
39 views

What's the largest sum of money using 5- cent and 7-cent coins that is not possible to create? [duplicate]

How do I know when I have hit the largest number? Is there any strategy better than guessing and checking that will work? Won't the numbers be infinitely large as there are an infinite amount of ...
user avatar
0 votes
0 answers
71 views

Intuition behind $\frac{a}{b} \equiv k \pmod{p} $

I am working with $p$-adic numbers at the moment and am having some trouble with a basic fact. I know that for $\frac{a}{b}\in\mathbb{Q}$ there is a solution $k\in\mathbb{Z}$ to $\frac{a}{b} \equiv k\...
user avatar
  • 31
-5 votes
0 answers
23 views

Quadratic Residue Modulo and Square Root [closed]

mod(56,101).sqrt() For some reason, this outputs 37, but when you manually solve it modulo first and square root after, it outputs 7.48. What could be behind this? ...
user avatar
0 votes
0 answers
17 views

Number Theory , Primes and sum of squares [duplicate]

Show that if $a^2+b^2≡0 \pmod{p}$ , with $p$ a prime number and $p≡3\pmod{4}$ Then automatically $a≡0\pmod{p}$ and $b≡0\pmod{p}$ What I have done so far, Suppose $a^2≡0\pmod{p}$ and $b^2≡0\pmod{p}$ , ...
user avatar
  • 37
1 vote
1 answer
80 views

How to find modular roots of $x^{22}-2x^{11}-x+2$ (to show it has more than $22$ solutions by CRT).

Consider a polynomial $P$ defined by $P(x)=x^{22}-2x^{11}-x+2,$ how to show that there exists an integer $n\geq1$ such that the equation $P(x)\equiv0$ modulo has more than $22$ solutions modulo $n?$ *...
user avatar
  • 81
0 votes
0 answers
17 views

Division Algorithm (Euclid's division lemma) proof for integers as a corollary

I've seen different proofs of a fundamental result commonly referred to as Division Algorithm or Euclid's division lemma. I've read a lot of different proofs on it, but I find one thing confusing. For ...
user avatar
  • 179
0 votes
0 answers
16 views

Show that the solutions are congruent. [duplicate]

Let $a \in \mathbb{Z}$ and $m \in \mathbb{N}$ such that $(a,m)=1$ if $x_1$ and $x_2$ are solutions of $ax+b \equiv 0$(mod m) show that $x_1 \equiv x_2$(mod m) I try to use the Bezout identity (with $(...
user avatar
2 votes
1 answer
47 views

Finding $(x,y)$ so that $3^{2x} + y \equiv 0 \bmod 10$

Prior information: $y = 2021k + 7$ $x = 1442k + 5$ My solution: I started from $3^{2x} + y \equiv 0 \bmod 10$. Calculated and simplified until I found this $-(1)^{k} + k + 7 \equiv 0 \bmod 10$. So $k =...
user avatar
-1 votes
1 answer
71 views

Can a Prime Number congruent to $3$ modulo $4$, when squared, be a non-trivial sum of two squares? [closed]

Problem : Can a Prime Number congruent to $3$ modulo $4$, when squared, be sum of two non-zero squares? Examples $11^2 = 121$ , can't be a sum of two non-zero squares $7^2 = 49$ , can't be a sum of ...
user avatar
  • 37
-2 votes
0 answers
26 views

Relating polynomials of the form x^2+a=0 mod p to other polynomials to find solutions [closed]

Some notes I found for an elementary number theory class mentioned solving quadratics in mod p by relating to another polynomial. For example, x^2+1=0 mod p was somehow related to x^4-1=0 mod p, and ...
user avatar
0 votes
1 answer
49 views

Find all triples $(a, b, c)$ of real numbers such that $a + 4b + 18c =\frac{a^2+b^2+c^2}{6}=2022$

Find all triples $(a, b, c)$ of real numbers such that $$a + 3b + 18c + min(a, b, c) =\frac{a^2+b^2+c^2}{6}=2022$$ There are three cases ( $a$ is min, or $b$ or $c$) Case 1: $a$ is min. We get $$2a + ...
user avatar
-1 votes
1 answer
34 views

How to handle modulus when there is division operation in the expression? [duplicate]

I am asked to print all numbers modulus of $1000000007$. My expression is $x*(1+f(x))/2$ For cases when x is even it is simple as i can do (x/2) first, then do: $ ((x/2)*(1+f'(x)) modulus 1000000007 $...
user avatar
3 votes
1 answer
53 views

Does this system of congruences have a solution? [duplicate]

I have the following congruence equation system: $$ \left\{ \begin{array}{c} x \equiv 7 \pmod{7} \\ x \equiv 4 \pmod{12} \\ x \equiv 16 \pmod{21} \\\end{array} \right. $$ I understand that: $$x\equiv ...
user avatar
  • 41
0 votes
2 answers
88 views

Find all possible solutions of $a^2+b^2+ab=1011$ [duplicate]

Find all possible solutions of $$(x-y)^2+(y-z)^2+(z-x)^2=2022$$ We can simply take $$x-y=a, y-z=b, z-x=-(a+b)\implies a^2+b^2+(a+b)^2=2022\implies a^2+b^2+ab=1011.$$ We can use modular arithmetic and ...
user avatar
  • 1,266
1 vote
1 answer
43 views

Alternate approach to a congurence problem

Show that positive integer $n$ of form $7k+1$, $7k+2$, $7k+5$ are the only possible solutions which satisfy that $n^5 + 4n^4 + 3n^3 = 7z+1$ for some positive integer $z$ ? My approach was taking n to ...
user avatar
0 votes
0 answers
21 views

A simple question concerning modular arithmetic [duplicate]

If we have a sequence such that Un=2mod4 if n is even, and Un=0mod4 if n is odd, and 2Un=28mod100 for all n in N, how can we find Un mod100?
user avatar
  • 85
1 vote
1 answer
45 views

Heegner Number Modular Arithmetic [closed]

Why are all Heegner numbers > 8 (up to 163) all equal 3, mod8 i.e Let $H$ denote a Heegner number. When $H$ > 8 $$H \equiv 3\mod8$$
user avatar
0 votes
1 answer
20 views

How to solve the following congruence property

The property reads: "$\phi(n) \equiv 2 ($mod $4$) when $n = p^a$ where $p$ is a prime satisfying $p \equiv 3$(mod $4$) and $a \ge 0$" I'm having difficulty going about proving this; if ...
user avatar
0 votes
1 answer
35 views

Computing the inverse of $16$ modulo $4n+1$, $n=1,2,\dots$ [duplicate]

For an integer $a$ and a positive integer $m$ with $(a,m)=1$, we can compute the inverse of $a$ mod $n$ by using the Euclidean algorithm. But is there a way to do this at once where $m=bn+c$ where $b,...
user avatar
  • 2,014
4 votes
0 answers
83 views

Does $x_1^{a_1}+\dots+x_k^{a_k}\equiv0$ always have no solution modulo some $m$.

Let $x_1,\dots,x_k\geq1$ be fixed integers. Does $$x_1^{a_1}+\dots+x_k^{a_k}\equiv0$$ always have no solution for integers $a_1,\dots,a_k\geq0$ modulo some integer $m\geq1$? The following proves the ...
user avatar
  • 5,463
-1 votes
0 answers
86 views

A system of cubic diophantine equations over positive integers

I was trying to solve an exercise and it led me to this system of equations: $$a^3 + b^3 = c^3 + x^3\\ c^3 + e^3 = a^3 + y^3\\ c^3 + d^3 = b^3 + z^3\\ c^3 + d^3 + e^3 = a^3 + b^3 + t^3$$ I need to ...
user avatar
  • 21
4 votes
1 answer
90 views

Prove using induction that ${p - 1 \choose n} \equiv (-1)^n \bmod p$ for $0 \leq n \leq p - 1$ where $p > 2$ is prime

Can someone see if this method is correct because I have doubts using the theory of induction? Let $p > 2$ be a prime number. Prove that \begin{align*} \binom{p-1}{n} \equiv (-1)^n \, (\mathrm{mod}...
user avatar
-1 votes
0 answers
23 views

why these 2 different modulo procedures produce same result? [duplicate]

I want to find result when apply modulo operation to this polynomial expression: $65\times(31^2 ) + 104\times(31^1 ) + 111 = 65800$ 65800 mod 101 = 49 by horner's method I can turn it into another ...
user avatar
  • 1
-1 votes
0 answers
12 views

Congruences mod 11 [duplicate]

I wanted to find $x$ so that $$ x\equiv 137^{165742} \mod 11 $$ and I got the hint $$ a^5\equiv \pm 1 \mod 11 $$ But why is that so? For $a=2n$ I have $$ 32x^5 \equiv -1 \mod 11 $$ but for $a=2n+1$ I ...
user avatar
-1 votes
2 answers
45 views

Find all lattice points $(x, y),$ such that $y \leq |x|$ and $y=\frac {x^2} {10}-\frac {x} {10} + \frac {9} {5}$ [closed]

Find all lattice points $(x, y),$ such that $y \leq |x|$ and $y=\frac {x^2} {10}-\frac {x} {10} + \frac {9} {5}.$ My attempt: Since,$y$ is an integer, $10\mid x^2-x+18$. But,I don't know how to ...
user avatar
  • 134
0 votes
2 answers
64 views

Chinese Remainder Theorem, discrete math problem [closed]

$5^{2003}$ $\equiv$ $ 3 \pmod 7 $ $5^{2003}$ $\equiv$ $ 4\pmod{11}$ $5^{2003} \equiv 8 \pmod{13}$ Solve for $5^{2003}$ $\pmod{1001}$ (Using Chinese remainder theorem).
user avatar
-1 votes
1 answer
61 views

Find all positive integers $n$ satisfying the following congruence

I have been asked to find $n$ satisfying $n^{17} \equiv n\;\;$(mod $4080$) I'm truly unsure how to even begin to attempt this. Is there a theorem or property of congruences that I should be ...
user avatar
2 votes
2 answers
215 views

The number of integer points on the curve $(7x-1)^2+(7y-1)^2=n$

The number of integral solutions to the equation $$x^2+y^2=n$$ is defined to be $r_2(n)$ and if $n=2^ap_1^{a_1}\dots p_k^{a_k}q^2$ where $p_i\equiv 1\mod 4$ and $q$ is the product of primes which are $...
user avatar
1 vote
1 answer
74 views

Is $y = \lim_{n \to 0} \left( x \bmod n \right)$ the same as $y = 0$? [closed]

My question is simply whether or not $$ y = \lim_{n \to 0} \left( x \bmod n \right) $$ is identical to $$ y = 0. $$ I don't have a formal education in either number theory or analysis, so I'm not sure ...
user avatar
0 votes
0 answers
56 views

Use of Fermat's Little Theorem

I have a question regarding the following use of Fermat's Little Theorem, quoted from Gallian's Algebra text: "One case concerned the number $p=2^{257}-1$. If $p$ is prime, then we know from ...
user avatar
1 vote
0 answers
45 views

Would encrypting a message twice with RSA with different keys be more secure that once?

This was a practice problem for a class. The class is over now and I never solved it, so I thought I'd ask here. Let's ignored the fact that adding extra security to single textbook RSA is unnecessary....
user avatar
-1 votes
0 answers
41 views

Math Question: How do I find Kate's seat number and Locker?

Thanks for helping! I have been struggling on this for the last week! I don't know where to start, How do I figure out the relationships? Can someone give me a step by step please?
user avatar
  • 11
-1 votes
0 answers
29 views

Primes and Modular Arithmetic [duplicate]

Let $p$ be a prime number and $s, r \in \{1, 2,..., p - 1\}$. Why $\exists_{i \in \{1, 2, ..., p-1 \}}$ $is \equiv p - r$ (mod p)? In one of the books, it was taken for granted, but I don't understand ...
user avatar
  • 1
1 vote
1 answer
66 views

Order of $U_{27}$, 2 Answers?

In my book I saw: $$U_{27} = \{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 25, 26\}.$$ I know that order of group is the number of elements inside that group, so we get an order of $...
user avatar
  • 139
4 votes
1 answer
92 views

Solving a depressed cubic polynomial in modulus. [closed]

Is there a general technique for solving depressed cubic modulus polynomial? For instance, how would you solve the equation $a^3 + a + 21 = 0 \pmod{43}$?. My attempts eventually ended up with solving $...
user avatar
0 votes
0 answers
40 views

A system of congruences

Suppose $x,y$ are integers in $[T,2T]$ and $U,V$ are different primes in $[2T^{2+\epsilon},4T^{2+\epsilon}]$ then consider the congruences $$U^2(x+y)^2=(aU^2+bUV+cV^2)\bmod (U-V)$$ $$UV(x+y)^2=(aU^2+...
user avatar
  • 6,047
3 votes
2 answers
155 views

Show that $7^6 \equiv 2^7 \pmod{223}$.

Given $7 \cdot2^5 \equiv 1\pmod{223}$. Show that $7^6 \equiv 2^7 \pmod{223}$. I know there must be some clever way to show this congruence. I can't seem to figure it out. I've considered that $224=7\...
user avatar
  • 1,281
2 votes
0 answers
34 views

Greatest prime that $p\mid n^2+3$ and $p\mid(n+1)^2+3$ [duplicate]

What is the largest prime number $p$ for which exists a natural number $n$ so that: $p\mid n^2+3$ and $p\mid(n+1)^2+3$ Given $p\mid n^2+3$ and $p\mid(n+1)^2+3$ then $n^2+3≡0\pmod p$ and $(n+1)^2+3≡0\...
user avatar
  • 73
1 vote
0 answers
69 views

How to calculate (20! * 12!) mod 2012 fast? [closed]

$(20! \cdot 12!) \mod 2012$ I calculated the answer multiplying each ${1 \cdot 2 \cdot 3\ldots n} $ with $\mod k$ one-by-one and found that the solution is $1684$. But I wonder if there is a faster ...
user avatar
  • 173
-5 votes
1 answer
53 views

If $u$ is a unit in $\mathbb{Z}_p$ for prime $p$, then $u^{p-1}=[1]$. Why? [closed]

As part of a proof of Fermat's little theorem, my teacher used that if $u$ is a unit in $\mathbb{Z}_p$ with $p=$ prime then $u^{p-1}=[1]$. Can someone help me understand why that statement is true?
user avatar
1 vote
1 answer
23 views

proof that $(b^n-1)/(b-1)$ is not prime if n is a pseudoprime not prime of the base $b$.

The question of my exercise says: Proof that, if $n$ is a pseudoprime not prime of the base $b$ (i.e. $b^{n-1}\equiv 1 (\mod n)$) then $N=(b^n-1)/(b-1)$ is also a pseudoprime not prime. I have proven ...
user avatar
  • 33
-1 votes
2 answers
51 views

Can I write a congruence like this?

I wrote down the following $\omega_e(P) \equiv 0,n\pmod{\! k}$, where $n|k$. What I'm trying to say is that $\omega_e(P)$ is either congruent to $0$ mod $k$ or $n$ mod $k$. Is this the correct way to ...
user avatar
-1 votes
0 answers
39 views

Remainder of $77!$ when divided by $79$ [duplicate]

I've got a question about how to find the remaider of $77!$ when divided by $79$. I tried it starting by its congruence modulo 79 $$77 \equiv 156\,(\mbox{mod}\,79)$$ $$77\cdot 76 \equiv 85 \,(\mbox{...
user avatar
2 votes
2 answers
66 views

prove or disprove: $((-2)^{(p-1)/2})^{p^{k-1}}\equiv \pm 1\bmod p^k\Leftrightarrow (-2)^{(p-1)/2} \equiv \pm 1 \bmod p$

Prove or disprove: if $p$ is an odd prime number and $k\ge 1$, then $((-2)^{(p-1)/2})^{p^{k-1}}\equiv 1\bmod p^k\Leftrightarrow (-2)^{(p-1)/2} \equiv 1\bmod p$ and $((-2)^{(p-1)/2})^{p^{k-1}}\equiv -...
user avatar
  • 871
-1 votes
0 answers
23 views

Check if $b$ is a divider of $a$ in modulus arithmetic [duplicate]

I have the following problem: Given a large number $x \equiv a\ \textrm{mod}\ p$ for a prime $p$ and another prime $b \neq p$, i want to know if $b \mid x$ only given $b, p$ and $a$. Is this even ...
user avatar
  • 99
2 votes
1 answer
57 views

Kernel and Image with $\mathbb{F}=\mathbb{Z}_2$ and $\mathbb{F}=\mathbb{Z}_3$

Let $V$ a vectorial space with dimension $3$ over a field $\mathbb{F}$ and let $End(V)$ the space of the linear operators of $V$. If the operator $f \in End(V)$ represents the matrix $$\begin{pmatrix} ...
user avatar
-1 votes
1 answer
72 views

Is there convincing numerical evidence for this conjecture?

Theorem: Every prime congruent to 1 (mod 4) can be written as the sum of two squares. e.g. 13= 3^2 + 2^2 29= 5^2 + 2^2 Conjecture: Any prime congruent to 4, 7, or 8 (mod 9) can be written as the sum ...
user avatar
  • 485
0 votes
1 answer
42 views

Prove that $\sum_{i = 1}^{N} 1+ (2i \bmod N) = N(N + 1) / 2$ for odd N.

I was able check by hand that for odd $N$ the $1+ (2i \bmod N)$ produces all values between $1$ and $N$ and for even $N$ there are repeats. But I've no ideas on how to write a mathematical proof for ...
user avatar

1
2 3 4 5
244