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
1answer
20 views

How to find the unknown $r$ from this congruence?

Find 𝑟 with $0≤𝑟<624$ such that $2^{82}≅𝑟$ mod 625. I have figured out that maybe we can use Fermat's little theorem to solve this question in which $r^{624}≅1$ mod 625. But I am kinda stuck in ...
-1
votes
0answers
34 views

Please help me answer this question. We are learning number theory and just went over modular arithmetic, prime numbers, and division. [closed]

Please help me answer this question. Can I use Fermat's Little Theorem to help me solve it? Maybe I can convert the equation to modular form but I do not know how to. I do not really know where to ...
0
votes
2answers
18 views

Solutions to a'th root of 1 mod p if gcd(a, p-1)=1 [duplicate]

Let $p$ be prime, and $a$ be an integer such that $gcd(a,p) = gcd(a, p-1)=1$. Show that the equation $x^a \equiv 1$ (mod $p$) has exactly one solution.
1
vote
2answers
30 views

Solution to congruence

I am studying abstract mathematics and I came across this in my textbook. Example: Find a solution to the congruence $$5x\equiv11\pmod{19}$$ It starts off the solution with: If there is a solution, ...
1
vote
2answers
31 views

How can I simplify $(n\,\mathrm{ mod }\,b^{k+1})\,\mathrm{ mod }\, b^k$? [duplicate]

I am trying to simplify an expression I've found that is related to converting from a number base to another: $$n\,\mathrm{ mod }\,b^{k+1} - (n\,\mathrm{ mod }\,b^{k+1})\,\mathrm{ mod }\, b^k$$ In ...
2
votes
1answer
45 views

Question 5.12 Tom M Apostol ( Introduction to analytic number theory) [duplicate]

This question is from textbook Introduction to Analytic Number Theory by Tom Apostol on page 127 and I am unable to solve it. Let p be a prime. Then prove that $\binom{n}{p}$ $\equiv \lfloor\frac{n}{...
-3
votes
0answers
16 views

suppose that g^a≡1(mod m),g^b≡1(mod m),prove that g^gcd(a,b)≡1(mod m) [closed]

enter image description here suppose that g^a≡1(mod m),g^b≡1(mod m),prove that g^gcd(a,b)≡1(mod m)
1
vote
1answer
15 views

How is Modulo used/defined under the sequence number function? Sequence Number Function and Hilbert's tenth problem

I'm trying to understand Hilbert's tenth problem and some of the proofs which show it is unsolvable. To date I've been using this paper and Hilbert’s Tenth Problem An Introduction to Logic, Number ...
0
votes
1answer
19 views

Suppose $P$ is the set of polynomials with coefficients in $\mathbb{Z}_5$ and degree less than or equal to $7$.

Question: Suppose $P$ is the set of polynomials with coefficients in $\mathbb{Z}_5$ and degree less than or equal to $7$. If the operator $D$ sends $p(x)$ in $P$ to its derivative $p'(x)$, what are ...
2
votes
1answer
57 views

HINT: $a^2+b^2=c^2$ cannot hold for $a,b$ odd and $c$ even. (using congruences) [duplicate]

Here is what I have: Suppose the contrary. Thus, (2k+1)(2k+1) + (2j+1)(2j+1) = (2p)(2p) Take mod 2 of both sides [1][1]+[1][1]=[0] [2]=[0] [0]=[0] No contradiction ... am I approaching this correctly? ...
0
votes
1answer
49 views

Modular quadratic equation help

our professor gave us one "equation to think at" (as he says). I tried to "think at" since friday but I don't know how to handle it properly and (if any) if there are solutions of ...
0
votes
4answers
52 views

Solve the following congruence: 2x ≡ 7 (mod 17) [duplicate]

Question Solve the congruence 2x ≡ 7 (mod 17). I have tried working out this problem but I am stuck midway. Could someone help me out by showing me or explaining how to proceed further? Here is the ...
3
votes
2answers
103 views

Is 0 and 1 invertible in modulo p?

Is 0 and 1 invertible in modulo p? I think 0 never is while 1 always is? E.g. 1 in modulo 13 is invertible to 13 and since 1*1=1 modulo 13.
0
votes
2answers
36 views

How can I prove they are congruent? [duplicate]

if $m$ is an integer and $\gcd(m,3)=1$,prove that $m^7\equiv m \pmod {63} $. I try using Fermat's Little Theorem,but it doesn't work. Please help me.
0
votes
2answers
41 views

Strings and Palindromes Counting

Hoping to check my work! How many length-5 strings have at least one each of the letters A,B,C. Meaning, it has to have at least one A, one B, and one C. I put down $3*3*3*2*1$. I thought so b/c you ...
1
vote
1answer
26 views

Prove that for any two numbers $0 \leq a < b \leq m - 1$ it is not possible that $m|b - a$ [duplicate]

As the title suggest im having difficulty approaching how or where to start proving this. Only thing i can derive from the given is that $m|b - a$ is equivalent to $b - a = mk$ for some k
0
votes
2answers
41 views

Computing the order of consecutive Fibonaccis, i.e. order of $f_n$ modulo $f_{n+1}$ [closed]

I believe I must incorporate $f_n^2=f_{n-1}f_{n+1}+(-1)^{n+1}$ somehow.
0
votes
0answers
25 views

Solving a system of equations with modulo n [closed]

How would you solve this system of equations with two unknowns $k$ and $d_A$ for $d_A$? The rest of the variables' values are known and all variables are $\in \mathbb{Z}$. I wanted to do equivalent ...
1
vote
1answer
55 views

Number theory problem with order

Let $p\in\mathbb{P}, a\in\mathbb{Z}$ such that $p\nmid a, ord_p a=d, k_0=\upsilon_p(a^d-1)$($\upsilon_p(a)=k$ denotes $p^k\mid a, p^{k+1}\nmid a$). Then prove that if $k\geq k_0$, then $ord_{p^k}(a)=...
-2
votes
0answers
35 views

A strange congruence [closed]

Suppose $p$ is a prime that satisfies $$p=1+b^k+b^{2k}+...+b^{nk}$$ for some $n,k>$ and $b>2.$ then prove that $$b^{p-1}\equiv 1+\frac{p-1}{(n+1)k}(b^{k}-1)p\pmod{p^{2}}$$ and $$b^{p-1}\not\...
1
vote
1answer
40 views

If all primes greater than some fixed value are congruent one modulo an integer, then said integer is equal two.

As in the title: Let $q$ be a positive integer, such that for all primes $p$, greater than a given natural number $N_q$, $p \equiv 1 \ \ (\text{mod } q)$. Then $q$ equals 2. I've thought about using ...
-2
votes
0answers
34 views

Distinct Digits when raised to a power of multiples of 10

Find $N$ such that the first $4$ digits of $n^{10000}$ are distinct .
1
vote
1answer
46 views

An identity on binomial coefficients

I have ran some experiments on Magma and I believe this is true: if $p$ is a prime number and $k, a \geq 0$ are integers then $${kp \choose ap} \equiv {k \choose a} \mod p^2.$$ Can anyone think of how ...
3
votes
2answers
38 views

Prove that {x ∈ Z : x ≡ 4 (mod 6)} ⊂ {x ∈ Z : x ≡ 0 (mod 2)}.

Let A:{x ∈ Z : x ≡ 4 (mod 6)} and B:{x ∈ Z : x ≡ 0 (mod 2)}. We have to show that A ⊂ B, meaning that all elements of A are in B but B contains at least one element that is not in A. I know that x ≡ 4 ...
1
vote
1answer
27 views

Solving equations with mod in Sage

I'm trying to use Sage to solve equations, but can't seem to get a toy example running. Lets say I want to solve for x, where ...
1
vote
0answers
31 views

Please critique my answer regarding Euler's theorem.

I was working on this problem to decipher a word encrypted using the RSA enciphering system. Long story short I had to find a modular exponent: $21865^{26767}$$mod$ $46927$ My Work I know that I can ...
1
vote
1answer
37 views

Primitive root modulo prime power

If I find $a$ is PR mod p, then a theorem states that either $a$ itself or $a+p$ is the PR mod $p^2$. Is there a fast approach to check the exponents of $a$, instead of going through every element in $...
-1
votes
2answers
22 views

Quotient remained Theorem question [closed]

Determine the number r, where $0\le r<m$, that makes the following true $15-7=r\pmod 8$. I am confused with this question as $A\bmod B=R$ which is the remainder
-2
votes
0answers
25 views

check if a number is a divisor of any repdigit [closed]

I am struggling with a problem in number theory. How to check if an integer $n$ is a divisor of any repdigit in base 10, that is a number made repeating a single digit, as 1111, 55, 333333, 88, ..
5
votes
1answer
78 views

Order of $\phi: g^i \mapsto g^{mi}$

Let $G = \langle g \rangle$ be a cyclic group of order $n$. Suppose $m$ is an integer such that $\gcd(m, n) = 1$. Define $\phi: G \to G, g^i \mapsto g^{mi}$. Then $\phi$ is (I think) an automorphism. ...
1
vote
5answers
51 views

Why is -8 $\equiv$ 6 mod 7?

I read in a book that $-8 \equiv 6 \bmod 7$ which means that $-8$ and $6$ leave the same remainder when divided by $7.$ The remainder when $-8$ is divided by $7$ is $-1.$ But when $6$ is divided by $7,...
5
votes
1answer
111 views

How to state and prove a certain result from modular arithmetic in algebraic terms?

Consider the group generated by the two functions $x\mapsto \frac 1x$ and $x\mapsto -1-x$. It is isomorphic to $S_3$ and contains the following elements: $$G=\left\{x,\frac 1x, -1-x,-\frac{1}{1+x},-\...
0
votes
0answers
61 views

Finding homomorphism between congruences $\bmod 18$ and $\bmod 3$

The (cyclic) multiplicative group $(\mathbb{Z}/18\mathbb{Z})^\times=\mathbb{Z}^\ast_{18}=\{1,5,7,11,13,17\}=<5>$ has an order $ord(\mathbb{Z}^\ast_{18})=6$ and based on Euler's theorem we can ...
0
votes
2answers
49 views

Is $(a \bmod N) \equiv (a \bmod x) \times (a \bmod y) $ where $x,y$ prime?

Can we say that for an $N$ where $N = xy$ and $x,y$ are prime $$(a \bmod N) \equiv (a \bmod x) \times (a \bmod y) ?$$
1
vote
0answers
28 views

Fast modular exponentiation $x^y \bmod 2^d$, $x$ is odd, $d\geq3$.

The task is to calculate $x^y \bmod 2^d$ in $O(d)$ summations/bitwise operations and 1 multiplication by $y$. The number $x$ is odd, $d\geq3$. I've found the proof that $x^{2^k} \equiv 1 (\bmod 2^{k+2}...
-1
votes
3answers
62 views

$437$ divides $16^{99} -1$. Help to finish it.

I am doing an exercise and find a question which I can't answer. The exercise asks to show that $16^{99}\equiv 1 \pmod{437}$. Since $\gcd(16,437)=1$, Euler's theorem says $$ 16^{\varphi (437)}\equiv 1\...
-2
votes
0answers
38 views

$n$-th element of a modular sequence

I have this question: Given a succession who works in this way: $x_0=45$ $x_{i+1}=(x_i + x_i^2)\bmod M$ Where $M$ is known and is an integer number and of course all the $x_i$ are integer numbers too. ...
2
votes
2answers
39 views

Find $a\in\Bbb Z$ such that $a^3\equiv 3 \pmod{11}$ without Fermat or Euler.

Find all $a$ integers such that $a^3\equiv 3 \pmod{11}$ I have this problem and I can't use Fermat or Euler theorems because we haven't seen them in class. I also have a solution that I don't ...
0
votes
3answers
61 views

Congruence, modular arithmetic

I am to show that from $a \equiv 16^{12 \cdot18}(\bmod 247)$, we have $a \equiv 8^{12 \cdot 18}(\bmod 247)$ $a \equiv 1(\bmod 247)$ How do I proceed here? I tried at first using Fermat's little ...
0
votes
0answers
10 views

Solutions of this set of linear congruences using Chinese Remainder Theorem? [duplicate]

Suppose m1, m2, ..., mk are positive integers > 1, not necessarily pairwise relatively prime. Also Suppose a1, a2, ..., ak ∈ Z. What can be said about the solutions of the following set of linear ...
-2
votes
0answers
29 views

How do you find use the totient function to find the numbers that are relatively prime to one number between two numbers?

For example, I know how to find all the numbers relatively prime to 300, up to 300. but lets say I wanted to find out how many numbers were relatively prime to 300 between 300 and 1500=(5*300)? How ...
0
votes
1answer
61 views
+50

Product of terms in Arithmetic Progression modulo $r$

Let $a_n = a_1 + (n-1)d$ be the $n$th term of an Arithmetic Progression. The product of the first $n$ terms is given by the formula, $$a_1 a_2 a_3 \dots a_n = \prod_{k=0}^{n-1} (a_1 + kd) = d^n {\...
0
votes
0answers
66 views

Varation of the Fermat's Little Theorem.

Someone incorrectly remembered Fermat’s Little Theorem as saying that the congruence $a^{n+1}≡a(\mathrm{mod}\,n)$ holds for all $a$ if $n$ is a prime. Describe the set of integers $n$ for which this ...
-1
votes
1answer
24 views

find if any number in A.P can be divided by a given number(k).

If there is any method other than finding each number of A.P iteratively and check if it is divisible by k or not? Example : Tn = 11*n+d; k = 7; find if (Tn % k == 0) ?
1
vote
0answers
30 views

Show that $n$ can be written in the form $n=c_{0}+c_{1}d+…+c_{k}d^{k}$ [duplicate]

I day ago, i've been solving some induction exercises from my textbook. But when i saw this, it seems a bit tricky and i couldn't come up with a solution. I hope someone can give clarity for this. ...
-1
votes
0answers
22 views

$A \in M_n(\mathbb{Z})$. $A_p$ being the image of $A$ in $\mathbb{Z_p}$, prove that $\text{rk} A\geq \text{rk} A_p$.

Question: Let $A ∈ M_n(\mathbb{Z})$. For any prime number $p$, let $A_p$ denote the image of $A$ in $M_n(\mathbb{Z}/p\mathbb{Z})$. Prove that $\text{rk} A ≥ \text{rk} A_p$ for all $p$, and the ...
2
votes
0answers
47 views

Show that $\phi$ is a homomorphism using modular arithmetic

The following proof should show that $\phi$ is a homomorphism, by making use of a modular arithmetic property: \begin{equation} (A+B) \mod {C} = (A \text{ mod C} + B \text{ mod C}) \mod {C} \end{...
-1
votes
0answers
38 views

Find the smallest positive integer that is congruent with −29 modulo 52.

I've been struggling with this question for about a week now and I can not seem to wrap my head around the concept of what the question asks. Any help of understanding the concept of a problem like ...
0
votes
1answer
32 views

Solving Quadratic, Cubic and Higher Degree Congruence Equations

I have a question about solving polynomial equations modulo some number. Say we were to solve the following quadratic congruence equation: $$x^2+x + 2 = 0 \quad mod \quad 4$$ We could of course just ...
-1
votes
0answers
41 views

Gaussian elimination with modular arithmetic

I'm wondering how the process for Gaussian elimination for augmented matrices changes when you have a system mod something For example say we have this big guy: $$\begin{bmatrix} 1 & 1 & 1 &...

1
2 3 4 5
218