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
2answers
31 views

Why for 7 | 5m+2n you can just make 7 | 5n+2n - 7n

Why for 7 | 5m+2n you can just make 7 | 5n+2n - 7n Why can you just add te 7n, and is it only true for whole numbers = n. Thank you for your answer
0
votes
4answers
59 views

Solving $39x\equiv75\pmod{102}$

Decide if a solution to the congruence $39x\equiv75\pmod{102}$ exists. As $\operatorname{hcf}(39,102)=3$ we can write the congruence as $13x\equiv25\pmod{34}$. Using Euclid's algorithm gives $1=5\...
3
votes
1answer
47 views

Finding integral basis of $K=\Bbb Q(\theta)$

Let $m$ be a cubefree integer. Set $m=hk^2$, where $h$ is square free, so that $k$ is square-free and $(h,k)=1$. Set $\theta=m^{1/3}$ and $K=\Bbb Q(\theta)$. Then an integral basis for $K$ is $$\{1,\...
2
votes
3answers
79 views

What is the remainder of $18!$ divided by $437$?

What is the remainder of $18!$ divided by $437$? I'm getting a little confused in the solution. It uses Wilson's theorem Wilson's Theorem: If $p$ is prime then $(p-1)!\equiv-1(\text{mod } p)$ ...
-3
votes
0answers
30 views

modulo calculation, prime numbers [duplicate]

I am trying to show that for every $x \in \mathbb{Z}$ it holds $x^5 \equiv x \text{ (mod } p$), for $p = 2,3,5$. Thanks.
0
votes
2answers
71 views

Find smallest $n$ such that $2^n \equiv 1 \pmod{51}$

From Euler's Theorem, I know that $2^{32} \equiv 1 \pmod{51}$, since $\varphi(51) = 32$. But, is there a way to efficiently calculate the lowest power of $2$, so that it is still congruent to $1 \pmod ...
-1
votes
3answers
711 views

Find all positive integers $n$ such that $n^4 − 1$ is divisible by 5. [duplicate]

Find all positive integers $n$ such that $n^4 − 1$ is divisible by 5. I want help with this problem. I have tried using factorization to $(n-1)(n+1)(n^2+1)$. but do not know how to proceed further. I ...
0
votes
1answer
20 views

How to prove that $|(kx\mod1)-(ky\mod1)|=k|x-y|$ under the following conditions:

Suppose that $k\in\mathbb{N}_{\geq2}$ and $x,y\in[0,1)$. Also assume that $|x-y|\leq1/(2k)$ and $|kx\mod1-ky\mod1|\leq1/2$. How do I prove that $$|(kx\mod1)-(ky\mod1)|=k|x-y|?$$
20
votes
0answers
404 views

Binomial coefficients modulo a prime

Consider an odd prime $p\equiv1 \pmod {16}$ and set $M=\frac{p-1}{2}$ for notational convenience. Then is there even a single prime $p$ of the above form for which the following congruence holds? $$\...
0
votes
1answer
40 views

Solution for quadratic congruence with $x^2 \equiv a \pmod p$

The question is to find the solution of $x^2 \equiv 796$ in $\mathbb{Z}_{797}$. I knew that we need to use the Euler criterion to check if the equation has a solution. Hence, I do know that this ...
-1
votes
1answer
40 views

Find the value of $f(2003)$ [closed]

If $f(11)=11$ and $f(n+3)=\frac{f(n)-1}{f(n)+1}$, find $f(2003)$.
2
votes
1answer
53 views

Property of a metric on $[0,1)$

This question is related to a question I posted earlier today (see here, this metric gives me nightmares), but I think it is easier to answer this one. Let $m\in\mathbb{N}_{\geq2}$ and consider the ...
0
votes
1answer
44 views

How to find the last digit of a number in base b?

For a number $a^{x^{...^n}} $. To find its last digit in a base b, Imagine that I have this number $a^{x^{y}}$ to simplify the problem. Then I calculate $a^{x} \equiv c \pmod b$ and after that $c^{...
1
vote
0answers
35 views

What is the Euclidian diameter of the following 'metric ball' in $[0,1)$?

Given an $m\in\mathbb{N}_{\geq2}$, define the map $f\colon[0,1)\to[0,1)$ by $f(x):=mx\mod1$. Using this map, for $n\in\mathbb{N}$ we define the metric $$d_n(x,y):=\max_{0\leq i\leq n-1}\min\{|f^{i}(x)-...
1
vote
0answers
22 views

Modular arithmetic: When is there guaranteed to exist a linear, bijective transformation between sets modulo a prime?

Given I have a prime number p, and two sets of distinct integers {k0, k1, k2, ... , km} and {h0, h1, h2, ... , hm}. All integers in these sets are nonnegative and less than p. I want to find a linear ...
0
votes
0answers
31 views

How do I generalize the product for the totient function to a slightly related function?

I already know that $\phi(n) = n\prod_{p\text{ divides }n}(1-\frac{1}{p})$. Suppose I define a closely related function $\phi(n,x;i,q)$ s.t. $\phi(n,x;i,q) = \sum_{1\leq j\leq x, \gcd(j,n)=1,j\...
1
vote
2answers
34 views

Solve the simultaneous systems of congruences for $x \equiv 10\pmod{60}, \;x\equiv 80\pmod{350}$

Solve the simultaneous systems of congruences for $x \equiv 10\pmod{60}, x\equiv 80\pmod{350}$ So the solution starts with $\gcd(60,350)=10$ then $10\mid 80-10$ because this is a requirement for ...
0
votes
0answers
37 views

Compute large powers a^m mod p; p prime [duplicate]

Please advise on a short cut on how to solve $$7^{3216645} \pmod {17}$$ by hand. So far I thought of using method of squaring and fast exponentiation (converting to binary form...) but these methods ...
1
vote
1answer
43 views

Find all the numbers and aware

A $3$-digit number $n$ is said and aware if the last $ 3$ digits of $n ^ 2$ are the same digits of $n$ and in the same order. Find all the numbers and aware I solved it with some nasty casework: We ...
0
votes
1answer
15 views

How to solve the number of solutions to a linear congruence modulo q?

How many $x$ less than or equal to $n$ are there when $x\equiv i(\text{mod }q) \equiv 0(\text{mod }p)$? I am just looking for an upper and lower bound.
1
vote
1answer
20 views

Prove $a + b = c \implies a \space (\text{mod } n) + b \space (\text{mod } n) \equiv c \space (\text{mod } n)$

Prove $a + b = c \implies a (\text{mod } N) + b (\text{mod } N) \equiv c (\text{mod } N)$ My attempt: $a = k_1 \space \text{ (mod n)}$ where $k_1$ is the remainder of $a$. $b = k_2 \space \text{ (...
1
vote
1answer
57 views

Modular Eqn-system with $3$ unknowns $(r,s,t)$: formula for the maximal solution $t$ (given $r$)?

This question focuses an unmentioned detail arosen in an earlier question, see this I've recently reread an older sketch of mine and reconsidered the following set of modular equations in ...
1
vote
2answers
52 views

Find the number of ordered $64-$tuples $(x_0,x_1,…,x_{63})$ such that $2017\mid (x_0+x_1+2x_2+3x_3+\dots+63x_{63})$

Find the number of ordered $64-$tuples $(x_0,x_1,...,x_{63})$ such that $x_0,x_1,...,x_{63}$ are distinct elements of $\{1,2,...,2017\}$ and $2017\mid (x_0+x_1+2x_2+3x_3+\dots+63x_{63}).$ My first ...
0
votes
0answers
54 views

Find three natural numbers $a,b,c$ such : $\begin{cases}ab=1(\mod c)\\ac=1(\mod b)\\bc=1(\mod a)\end{cases}$ [duplicate]

Question : Find three natural numbers $a$, $b$ and $c$ such that the remainder of the euclidean division of the two numbers (of these numbers) by the third number is $1$ Mean : $$\begin{cases}...
0
votes
0answers
35 views

Topological entropy of $[0,1)\to[0,1), \ x\mapsto mx$ modulo $1$

Let $m\in\mathbb{N}$ such that $m\geq2$. How do I calculate the topological entropy of the map $E_{m}\colon[0,1)\to[0,1)$ defined by $$E_{m}(x)=\begin{cases}mx&0\leq x<1/m\\ mx-1&1/m\leq x&...
1
vote
1answer
45 views

If $f(f(x))$ is linear, is $f(x)$ linear? If f(x) is closed on the set of natural numbers?

If I have a function defined on the natural numbers $\mathbb Z_{>0}$, does $f(f(x))=ax+b$ imply that $f(x)=rx+q$, where $a,b,r,q$ are naturals? This came to mind in the context of a different ...
1
vote
0answers
26 views

Notation of how many times an expression is true

first time posting on here so apologies if I'm breaking formatting rules or something. Also, I'm not a native English speaker, yadda yadda. So a few years ago I found something in school when the ...
0
votes
1answer
31 views

Explicit solution to modular equation

I have the following modular equation, $$ (p + a) \mod 3 = m$$ which I want to solve for $a$. Of course, there are many valid values for $a$, but since I assume $m,p \in \{ 0, 1, 2\}$, I only want ...
0
votes
2answers
26 views

find the last digit of X in base Y

If X is a number in decimal system how will we find the last digit of X in base Y. for eg $X = 12$ and $Y = 9$ 12 is 13 in base 9 and last digit of 13 is 3. Can we make a formula for this?
0
votes
1answer
17 views

Consecutive application of Modulo Operator

Is it true that $a \bmod n\equiv (a \bmod n)\bmod n$? Is is possible to show intuitively why ?
0
votes
2answers
45 views

How to find the LCM of numbers with exponents?

I would like to know if there is a mathematical approach to finding the LCM of $(29^{17} +2 , 29^{17} -1)$? Even if we would rearrange it to a fraction of the form $\frac{(29^{17} +2)\cdot (29^{17} ...
1
vote
1answer
69 views

How many prime $p$ that not satisfy with any integer $x$ in $x^3-2028x+2018\equiv 0 \pmod{p^3}$

From the topic , how many prime $p$ that cannot find any integer $x$ to satisfy $$x^3-2028x+2018\equiv 0 \pmod{p^3}$$ I try to start with $x^3-2028x+2018\equiv 0 \ \ \left (mod \ p \right )$ and ...
3
votes
1answer
35 views

If $P$ is an odd prime number such that $P=2k+1$, then prove $(k!)^2\equiv (-1)^{k+1} \mod P$

A question I have been given for an assignment is as follows. If $P$ is an odd prime number such that $P=2k+1$, then prove $(k!)^2\equiv (-1)^{k+1} \mod P$ Hint: Try to see how to group the terms ...
1
vote
3answers
32 views

Quadratic Modular Arithmetic [duplicate]

I want to prove that $$ w^2 \equiv 2 \quad (\bmod{5})$$ has no solutions in integers. What I tried: $$ w^2 \equiv 2 \quad (\bmod{5})$$ $$ \Rightarrow w^2 = 2 + 5k, \quad k \in \mathbb{Z} $$ Now, I ...
1
vote
2answers
44 views

What is the correct name for “complement of modulus” function, $f(n) =m - n\ \mathrm{mod}\ m$?

What is the name of the function $f$, defined below? $$f(n) = m - n\bmod m$$ or $$n\bmod m + f(n) = m $$ If I were to make up a name, I would probably choose "complement modulus," and maybe $\...
2
votes
1answer
24 views

Find $[\Bbb Z_{40} : \langle[12], [20]\rangle]$

Find $[\Bbb Z_{40} : \langle[12], [20]\rangle]$ So I believe that the question is talking about the smallest subgroup which contains $12, 20$ which I believe is $\langle 4 \rangle$ What next?
1
vote
3answers
34 views

if $a \equiv 1 \pmod 3$ and $a \equiv 1 \pmod 4$, then $a \equiv 1 \pmod {12}$ [duplicate]

I was working on a proof when I came to portion where I need to prove that if $a \equiv 1 \pmod 3$ and $a \equiv 1 \pmod 4$, then $a \equiv 1 \pmod {12}$. I'm only familiar with working with the ...
1
vote
2answers
43 views

Then find the sum of all possible values of $abc$.

Let $a, b, c$ be positive integers with $0 < a, b, c < 11$. If $a, b, $ and $c$ satisfy \begin{align*} 3a+b+c&\equiv abc\pmod{11} \\ a+3b+c&\equiv 2abc\pmod{11} \\ a+b+3c&\equiv 4abc\...
1
vote
1answer
55 views

$5a + 2b \equiv 0 \pmod 7$ is Symmetric?

I have a problem regarding the understanding of modulus. so someone proved $5a + 2b \equiv 0\pmod 7$ is symmetric using the modulo circle, and my brain cant comprehend how he meant that. im talking ...
0
votes
0answers
7 views

Values that “almost” satisfy the Carmichael function, but aren't minimal

The Carmichael function is $\lambda(n)=k$ where $k$ is the smallest number satisfying the congruence $x^k\equiv1\mod{n}$ for all $x$ coprime to $n$. Is it possible to compute an increasing sequence of ...
-2
votes
1answer
26 views

how to calculate ((13)^15)^17 mod 17 using fermat's little theorem? [duplicate]

How to calculate ((13)^15)^17 (mod 17) using fermat's little theorem?
1
vote
1answer
63 views

Three-variable modular diophantine problem - what is the set of solutions? Is there any matrix ansatz meaningful?

I'm rereading some older unfinished material again. I had the following problem which I still can only access by brute force and would like to -at least- understand more about an analytical access. ...
1
vote
3answers
74 views

solve $11^x ≡ 21 \pmod {71}$

Solve $11^x ≡ 21 \pmod {71}$ I am supposed to create a chart with $j$, $11^j$ and $21\cdot 11^{-9j}$ I have filled out the first 2 rows, but can not figure out the 3rd row. This is what I have so ...
3
votes
1answer
45 views

When $n>1$, there is no ordering $<$ on $\mathbb{Z_n}$ such that…

When $n>1$, there is no ordering $<$ on $\mathbb{Z_n}$ such that: for all $[a]_n,[b]_n\in\mathbb{Z_n}$, we have exactly one of $[a]_n<[b]_n,[a]_n=[b]_n,$ or $[b]_n<[a]_n$; if $[a]_n<[b]...
-1
votes
1answer
61 views

$2^{947} (\bmod 1373)$ [duplicate]

I have that $2^{947} (\bmod 1373)$ how does one solve this without a calculator? Can you separate it into nice $2^x2^y$ or $(2^x)^y$? I'm really not sure how to go about this problem. Thanks for any ...
1
vote
0answers
16 views

Number of distinct periods of LCG

I'm looking for the number of distinct periods of a LCG $$ \lambda(a, c, m) := {X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}} $$ A period $a = a_1, a_2, a_3 \ldots a_n$ is different from a period $b = ...
1
vote
4answers
33 views

How do I find the remainder for the following?

I know this is a very typical question for modular arithmetic but still I haven't found a comprehensive explanation for this question, so I'm posting it here. So here goes: I need to find the ...
0
votes
0answers
31 views

Exponentiation of a modulo sum

Suppose a finite field in $F_p$, $p$ being a large prime and $g$ a generator of the field. Let two parts $A$ and $B$,with $A$ knowing a secret $a \in F_p$ and $B$ knowing another secret $b \in F_p$. ...
0
votes
1answer
57 views

Bezout's Identity and inverse modulo proof (GCD) [duplicate]

So might be a dumb question and actually quite simple, but I managed to confuse myself, and I don't really want to be learning the wrong thing. So $a≡b\;(\bmod n)$ can be defined by $a-b=ln,$ $l\in\...
0
votes
0answers
15 views

counting integers in modular function

Given a set of n positive integers. Say A={ 3,4,6,7,8} We have to find a number of integers in set that follow this property. property { factorial(x) mod (x+1) = x } here 3 and 7 are those numbers. ...