Skip to main content

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

How do you parameterize simultaneous solutions to equations with expressions like "$ x +2 \left\lfloor\frac{x}{3}\right\rfloor + 1 - [3 \mid x]$"?

Let all functions be integer functions herein. I.e. $\Bbb{Z}\to\Bbb{Z}$ or $\Bbb{N}\to\Bbb{Z}$ where appropriate. I found this jewel of floor functions. So that made me wonder whether, we can solve ...
SeekingAMathGeekGirlfriend's user avatar
0 votes
0 answers
32 views

The prime race $a_i \mod 11$ vs $b_i \mod 11$ conjecture

Let $f(n,a)$ be the number of primes of type residue $a \mod 11$ between $1$ and $n$. Is it true that for all $n>1$ we have $$f(n,1)+f(n,2)+f(n,3)+f(n,5)+f(n,7)+f(n,6)+f(n,8) > f(n,4)+f(n,9)+f(n,...
mick's user avatar
  • 16.2k
-2 votes
1 answer
76 views

Is there a way to show that the Fibonacci subsequence $F_{6n+2}+2$ can't have any square number? [closed]

I'm investigating the Fibonacci sequence $F_{6n+2}+2$. I searched, by Maple, the first $10000$ numbers. I couldn't find any squares. I tried using quadratic residue and modularity but I got nothing ...
ThePirateKing's user avatar
0 votes
0 answers
17 views

Existence of $n$ where $S_b(n^k) \equiv r \bmod M$ where $S_b$ denotes sum of digits in base $b$

Let $b, k, M \in \mathbb{N} \setminus \{1\}$, $r \in \{0, 1, \dots M-1\}$ and $S_b: \mathbb{N}_0 \rightarrow \mathbb{N}_0 $ denote the method which outputs the sum of digits of its input in base $b$. ...
EnEm's user avatar
  • 1,017
-1 votes
0 answers
52 views

Where does this method for calculating $2^{483}\pmod {2021}$ fail?

Using square and multiply we can verify that $2^{483} \equiv 988\pmod{2021}$. However, we can also verify that $2^{966} = 2 \cdot 2^{483} \equiv 1\pmod{2021}$. In that case $2^{483} \equiv 2^{966} \...
Kris's user avatar
  • 25
1 vote
0 answers
16 views

find the other lines that intersect a set of evenly-spaced points along a line on a torus

i have a square, side length $2\pi$, and i'm drawing lines on it that wrap around when they reach the edges - this is of course equivalent to the surface of a torus. the lines are straight lines that ...
Silver's user avatar
  • 111
2 votes
2 answers
49 views

Solving quadratic modular equations

I am interested in how to solve equations of the form $x^2 \equiv d \mod p$. I did try to read into the topic. In the book I am reading one is introduced to the Legendre-Symbol, then to the Jacobi-...
NTc5's user avatar
  • 553
3 votes
1 answer
52 views

Prove that $2^𝑎 + 3$ is divisible by $2^{𝑎 + 𝑏} − 9$ only if $𝑎 = 𝑏 = 2$

For $a$ and $b$ positive integers, I want to show that $2^𝑎 + 3$ is divisible by $2^{𝑎 + 𝑏} − 9$ only if $𝑎 = 𝑏 = 2$ and no other solutions exist. Note that I am only interested in the case ...
blu potatos's user avatar
1 vote
0 answers
66 views

Primes of the form 2...21

I was wondering what properties could have these numbers: $21, 221, 2221, 22221, ...$ At glance I thought this set would have infinitely many primes. Immediately I went to Python and I realized that ...
Francisco Javier Maciel Hennin's user avatar
1 vote
1 answer
37 views

Number of solutions to underdetermined system of equations in modular arithmetic vs real or complex valued equations

I just watched this video about solving a video game puzzle using matrices defined over the integers mod 3, which essentially ended up being a lesson about how the usual rule, that square matrices ...
Mikayla Eckel Cifrese's user avatar
-1 votes
0 answers
31 views

Find the remainder when $(1!1) + (2!2) + (3!3) +...+(286!*286)$ is divided by $2 ^ 4 * 5 ^ 3$. [duplicate]

I did this $1×1! = 2! - 1!, 2×2! = 3! - 2!$ and so on then by telescoping I get $287! - 1!$ so as $287!$ is divisible by $2000$ so got the remainder as $1999$, but the answer is given $08$. So please ...
Shubhank agase's user avatar
2 votes
0 answers
19 views

Simple divisibility question [duplicate]

I want to find all $k$ such that for every pair of positive integers $(m, n)$, $(km + n) \mid{} (kn + m) \implies m \mid{} n$. Here are my ideas so far: Say that $(km + n) \mid{} (kn + m)$. Then ...
Christopher Miller's user avatar
4 votes
0 answers
142 views

Can we efficiently compute $a!\mod b$?

It is well known that we easily can compute , say , $2^a\mod b$ for large integers $a,b$. We can use the repeated square method which gives a fast result even if $a,b$ have , say , $50$ decimal digits....
Peter's user avatar
  • 85k
0 votes
0 answers
47 views

Find the reminder of a very large number (power of to the power of to the power of etc) [duplicate]

How would you approach the following problem? I've tried to focus on last digits for example but that didn't lead me to the answer (Like, 2021^(any number) will have last digit 1). Can you guys give ...
Prim3numbah's user avatar
0 votes
0 answers
50 views

MOD of a negative number [duplicate]

-- I checked the other similarly titled questions, they are not duplicates. I was playing around, and noticed that in Excel if I did 5%(-4) (I used function of "=MOD(5,-4)") that the answer ...
Doragon's user avatar
  • 133
4 votes
1 answer
86 views

how to find expression of $a\text{ mod } n$ using polynomial of $e^{\frac{2a\pi i}{n}}$?

I tried to find a polynomial for $a\text{ mod } n$ (for $a,n\in N$) by using powers of $\exp\left(\frac{2a\pi i}{n}\right)$ which mean find the coefficients $f(n,k)$ in $$ a\text{ mod } n=\sum_{k=0}^{...
Faoler's user avatar
  • 1,477
1 vote
0 answers
46 views

number theory, binomial coefficients divisibility

Let $p$ be a prime number greater than $3$ and $n$ a positive integer. Suppose $\nu _p(n) = r$. Prove that $\dbinom{np}{p} - n$ is divisible by $p^{3+r}$ The problem is here: https://poti.impa.br/...
amkpm90's user avatar
  • 352
3 votes
3 answers
91 views

how can I solve the equation $19^x+23^y=100z$ for integers $x,y,z$?

I tried to find all solution for integers $x,y,z$ $$19^x+23^y=100z$$ I tried by using $mod$ operation by taking $\mod20$ and I get $$ 3^y\equiv_{20} (-1)^{x+1}$$ where $\equiv_{n}$ means both sides ...
Faoler's user avatar
  • 1,477
2 votes
2 answers
105 views

Number of polynomial functions in $\mathbb Z/2\mathbb Z[x_1, \, \ldots, \, x_n]$?

What is the number of polynomial functions in $\mathbb Z/2\mathbb Z[x_1, \, \ldots, \, x_n]$? (Here I define $p \sim q$ iff $p(x) = q(x)$ for all $x$.) What about the case if we allow permutations? ...
Markus Klyver's user avatar
2 votes
1 answer
66 views

Polynomial Divisibility by Factorial Plus One [closed]

Find all polynomials with integer coefficients $f$ such that $f(p) \mid (p-1)! + 1$ for all primes $p$. Using Wilson’s theorem we find that $f(p)=p;-p$ satisfy the problem. I also thought about using ...
math.enthusiast9's user avatar
0 votes
1 answer
56 views

For each integer $k,$ does there exist a $k-$tuple of primes, $(p_n)_{n=1}^{k},$ s.t. for each $n,\ p_{n+1}=2p_n- 1$ or $p_{n+1} =2p_n+1?$

For each $k\in\mathbb{N},$ does there exist a $k-$tuple of primes, $(p_n)_{n=1}^{k},\ $ such that for each $n,$ the following is satisfied: $p_{n+1} = 2p_n- 1\ $ or $p_{n+1} = 2p_n + 1?$ If yes then ...
Adam Rubinson's user avatar
0 votes
0 answers
18 views

general form for effective magazine size with refunded bullets

This exploration started because of the video game destiny, in which weapons can have essentially magical perks, such as every 3rd shot hit, add one bullet back into the magazine. What I am curious ...
Cat Girl's user avatar
1 vote
1 answer
95 views

distribution of square roots of unity $mod n$ | Factoring with inverse pair

I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where $$ dc \equiv 1 \pmod{\phi(N)}, $$ there exists a ...
FieldHouser's user avatar
0 votes
0 answers
43 views

Confusion about replacing a variable in a expression of parameters

I have the following problem: I have a diophantine equation of the form: $$f(x,a,b)+c=0.........(**)$$ and by reducing it modulo $p^n$ I get a congruence of the form $h(x,a,b)+c\equiv 0\pmod {p^n}$ ...
Safwane's user avatar
  • 3,844
0 votes
2 answers
35 views

Find two variables from known modulo equation and arithmetic equation.

Given two equations like these: $P \bmod Q = 90$ $P - Q = 9900$ How to find $P$ and $Q$ value? Edit (Using subtition): $ P \bmod Q = 90 $ $ P = 90 \bmod Q $ $ 9900 + Q = 90 \bmod Q $ Here I'm stuck.....
Muhammad Ikhwan Perwira's user avatar
0 votes
0 answers
37 views

Show $65$ is an Euler-Jacobi pseudoprime to the base $b \iff b^{2} = \pm 1 \mod 65$

Say $(b,65) = 1$. I want to show that $$65 \text{ is an Euler-Jacobi pseudoprime to the base }b \iff b^{2} = \pm 1 \mod 65$$ that is, $$b^{(65-1)/2} = b^{32} \equiv \left( \frac{b}{65} \right) \mod 65 ...
Robin's user avatar
  • 3,940
0 votes
0 answers
30 views

Why is it that for prime factors $p_i$ of a Carmichael number $n$, the identity $(p_i - 1) \mid (n-1)$ holds? [duplicate]

Carmichael numbers are composite $n$ for which $$a^{n-1}\equiv1\quad(mod\ n)$$ is true for every prime $a<n$. Part of a proof I'm currently working through includes the condition that for ...
299792458's user avatar
  • 243
2 votes
1 answer
49 views

Struggling with modular arithmetic problems. [duplicate]

I've been struggling with this modular arithmetic problem for a while, I could solve the simpler problems where we have to find out what day it is or what hour is is after a certain amount of time has ...
Slime's user avatar
  • 75
-1 votes
0 answers
22 views

(Modular Arithmatic) Modular Congruence [duplicate]

I'm working through some challenges on cryptohack.org and am new to modular arithmetic. They describe it in the following terms: Formally, "calculating time" is described by the theory of ...
Austin Wile's user avatar
4 votes
1 answer
166 views

Show that there are only finitely many pairs of positive integers $(n, m)$ such that $d(m!) = n!$.

Show that there are only finitely many pairs of positive integers $(n, m)$ such that $d(m!) = n!$, where $d(n)$ denotes the number of positive divisors of $n$. My approach (it isn’t complete and ...
math.enthusiast9's user avatar
0 votes
1 answer
60 views

Let $x$ and $y$ be non-negative integers such that $N =2^6 + 2^x+2^{3y}$ is a perfect square and $N\leq10,000$. Find the maximum value of $x+y$.

Let x and y be non-negative integers such that $2^{6}+2^{x}+2^{3y}$ is a perfect square, and the expression should be less than 10,000. Find the maximum value of $x+y$ $2^{6}+2^{x}+2^{3y} <= 10,...
Jacob Phan's user avatar
0 votes
0 answers
26 views

Confused on one step of the proof (final decimal digit of the square of an integer, from Rosen's Discrete Math Textbook) [duplicate]

From Rosen's Discrete Math Textbook: Formulate a conjecture about the final decimal digit of the square of an integer and prove your result. Solution: The smallest perfect squares are 1, 4, 9, 16, 25,...
Bob Marley's user avatar
0 votes
0 answers
37 views

Cyclicity of k digits in Powers of 3

To show : The last k digits of ${3}^a$ and $3^{a +4×5^{k-1}}$ are same. $$OR$$ ${3}^a$mod(${10}^k$) = $3^{a +4×5^{k-1}}$ mod(${10}^k$) It can be true or false I don't know. I was solving another math ...
user389250's user avatar
1 vote
1 answer
80 views

The least common multiple of four numbers is equal to their sum

Problem: The greatest common divisor of four positive integers, not necessarily distinct, is equal to 1. Their least common multiple is equal to their sum. Find the number of possible values of the ...
Jacob Phan's user avatar
2 votes
3 answers
154 views

$4^n$ is not a sum of four distinct squares

The famous theorem of Lagrange tells us that any natural number can be written as a sum of four squares, where the summands are not necessarily distinct. After some experiments, I have concluded that $...
RFZ's user avatar
  • 17k
0 votes
3 answers
63 views

A crew needs to divide oranges [duplicate]

A boat sinks in the ocean and the 5 survivors each jump into a different lifeboat. They agree to meet on the deserted island pointed out in the distance. The next morning, the first castaway walking ...
whyu's user avatar
  • 19
2 votes
3 answers
96 views

How to integrate $\int\frac{|x|+5}{|x|+8}dx$?

How to integrate $$\int\frac{|x|+5}{|x|+8}dx$$ ? I am trying to integrate this above expression by assuming the above integral to be $I$. Therefore, $$I=\int\frac{|x|+5}{|x|+8}dx$$. When $|x|=x$, $$I=\...
Dropper's user avatar
  • 129
1 vote
0 answers
38 views

Counting solution to congruences

I want to count the $x, y \mod a$ and $r, s \mod b$ subject to the following conditions (defining $u, v, w, k$ which exist by the coprimality conditions) $$(a, x, y) = 1$$ $$(b, r, s) = 1$$ $$ as+xr+...
TheStudent's user avatar
  • 1,283
0 votes
0 answers
34 views

Intuition behind terms in Chinese Remainder Theorem solution formula [duplicate]

Given the following equations: $$ a = 2 \ (mod \ 5)$$ and $$ a = 3 \ (mod \ 13)$$ Let $a_1=2$, $a_2=3$, $n_1=5$, $n_2=13$, $m_1=13$, $m_2=5$ Let $m=5 \times 13=65$ Let $$c_i = m_i * (m^{-1}_i mod \ ...
jam's user avatar
  • 81
0 votes
0 answers
77 views

Prove that $U(40)/U_8(40) $ is cyclic but $U(40)/U_5(40)$ is not cyclic.

I was reading the chapter about Factor groups in Joseph A. Gallian's Contemporary abstract algebra and I ran into the following problem. $$\text{Prove that }U(40)/U_8(40) \text{ is cyclic but } U(40)/...
Selim Bamri's user avatar
-1 votes
1 answer
52 views

Calculate (10a) mod m without calculating 10a [duplicate]

Given $10<a<m<10a$, is it possible to calculate $10a \pmod{m}$ without calculating $10a$ ($a$ and $m$ are very big numbers)? Note that the formula $$ab \pmod{m}=((a \pmod{m}) \cdot (b \pmod{m}...
Chezi's user avatar
  • 17
3 votes
1 answer
176 views

Suppose that there exists infinity prime $p_i$, such that $a$ is congruent to a power of $2 \bmod p_i$, does $a$ need to be a power of $ 2$?

Let $a$ be an integer. Suppose there exists infinitely many primes $\{p_i\}_{i \in \mathbb N}$ such that $a \equiv 1 \pmod{p_i}$, then it's clear that $a$ has to equal to $1$. Now, suppose there ...
ghc1997's user avatar
  • 1,561
1 vote
0 answers
51 views

Squares in $(\mathbb{Z}/p^n \mathbb{Z})^\ast$ in terms of squares in $(\mathbb{Z}/p \mathbb{Z})^\ast$

Let $p$ be an odd prime and $n$ be a positive integer. For a ring $S$, let $S^\ast$ denote the set of units in $S$. It is known that $x$ is a square in $(\mathbb{Z}/p^n \mathbb{Z})^\ast$ if and only ...
jimm's user avatar
  • 1,027
3 votes
0 answers
79 views

Repeated application of the map $x \mapsto 2^x \bmod x$

Recently, I've been playing around with the map $x \mapsto 2^x \bmod x$. I calculated the smallest natural number requiring $n$ application of this map to reach $0$, and here's that sequence: $$0, 1, ...
Bryle Morga's user avatar
  • 1,029
0 votes
0 answers
48 views

Last $4$ nonzero digits of $n!$ in base fourteen

Question: What are the last $4$ nonzero digits of $2025!$ in base fourteen? Note: This is not a contest/homework question. I know how to find the number of trailing zeroes in base fourteen, so $2025!$ ...
Thirdy Yabata's user avatar
1 vote
0 answers
55 views

Do polynomials taken modulo integers compose?

Intuitive Idea: Say we have polynomials modulo positive integers; for instance, $f(x) = 3x + 1\pmod 5$ and $g(x) = 5x^2 - x + 3 \pmod 7$. (Yes, there is some abuse of notation here.) We may "...
Isaac Cheng's user avatar
0 votes
2 answers
96 views

$H \leqslant (\Bbb{Z}/n)^*$ the square roots of $1$, with $n$ squarefree; what's size of pseudocoset $kH\subset \Bbb{Z}/n$ where $k$ is any integer

Consider the ring $\Bbb{Z}/n$ for square-free $n$. Then the multiplicative subgroup $H \leqslant (\Bbb{Z}/n)^*$ given by $H = \{ x \in \Bbb{Z}/n : x^2 = 1 \pmod n\}$ has size exactly $|H| = 2^{\omega(...
SeekingAMathGeekGirlfriend's user avatar
3 votes
3 answers
85 views

Prove that number $(4n-1)(2n-1)(2n+1)(4n+1)$ is not a perfect square.

the problem Prove that whatever $n$, a non-zero natural number, the number $(4n-1)(2n-1)(2n+1)(4n+1)$ is not a perfect square. my idea I tried working with modular arithmetic in congruences modulo 4, ...
IONELA BUCIU's user avatar
  • 1,125
1 vote
0 answers
26 views

How to programmatically perform multivariate polynomial division modulo 2.

I'm trying to write code to do multivariate polynomial division modulo-2 (so no coefficients or degrees). Say I have the polynomial $xyzw + yz$ and want to divide it by $xw + xwz$. IIUC, the usual ...
Aaron's user avatar
  • 111
0 votes
0 answers
24 views

Congruences of partition function

I'm trying to understand Ken Ono's results showing Erdös' conjecture for the primes $\ge5$. He first shows the following: let $m\ge5$ be prime and let $k>0$. A positive proportion of the primes $\...
CarloReed's user avatar

1
2 3 4 5
228