Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
1answer
40 views

Inverse of a bijective function involving cases

In continutation to a question that i asked earlier and got answered here :Discretizing a mathematical equation This is a bijective mapping from the set of ordered tuples $(x,y,z)$ where each $x,y,z\...
0
votes
2answers
31 views

Order of a polynomial root

I'm reading this pdf about finite fields. In the first page it's said: Let $α$ be a root of $f(x)$. Then $f(x)|x^{n}-1 \Rightarrow ord(a)|n $ However, what is the order of a root in this case ? ...
0
votes
1answer
26 views

Powers when working with primitive polynomials

When we work with polynomials modulo $m(x)$ where m(x) is a primitive polynomial over $GP(p^{m})$, i know that i can take every coefficient of any polynomial and replace it with it's congruent modulo $...
1
vote
1answer
55 views

A really nice and elementary conjecture involving numbers

Yesterday, i discovered a nice thing while playing with numbers. It is trivial to note that $\forall n\in \mathbb{Z^+},\exists x,y\in \mathbb{Z}$ such that $3^n=5x^2+y$ has solutions. Also, ...
0
votes
1answer
23 views

Polynomial rings and congruence classes

Let's consider the polynomial $m(x)$ over a field $\mathbb{Z}_{3}$. We know that $[m(x)]_{m(x)}=m(a)=0$. Now $m(x)=x^{3}+1$; in my lectures slide, it's said at this point that: $m(a)=0$ implies that ...
2
votes
1answer
38 views

Modular arithmetic equation system

Assume I have the following modular congruences, where $n = pq$ is the product of two (large) primes: $$A \equiv (xp+yq)^{e_1} \mod n$$ $$B \equiv (zp+uq)^{e_2} \mod n$$ We know $A,B, x,y,z,u, e_1, ...
0
votes
1answer
22 views

Negative integers and polynomial congruence classes

Let's take a polynomial $m(x)$ from $\mathbb{Z}_{3}[x]$. Now, $\mathbb{Z}_{3}$ should contains the integers $-1,-2,-3$. However after reading few exercises about this argument i suspect that we can ...
0
votes
1answer
28 views

Polynomials with coefficients in a field

Let's consider this theorem: Let $f(x)$, $g(x)$, $p(x)\in F[x]$ with $p(x)\neq 0$. We say $f(x)$ is congruent to $g(x)$ modulo $p(x)$ if $p(x)$ divides $f(x)−g(x)$, and we write $f(x) \equiv g(...
2
votes
1answer
56 views

Find the condition on $p$ such that equation $x^2+3 \equiv 0 \pmod{4p^2}$ has roots

Problem: Find the condition on $p$ such that equation $x^2+3 \equiv 0 \mod 4p^2$ has roots with $p$ is a prime and find the number of roots of this equation. My solution: $x^2+3 \equiv 0 \mod 4p^2 \...
0
votes
0answers
32 views

An elaboration of a part in the proof of a criterion for finding Carmichael numbers.

The criteria and its proof is given below: But I do not understand why $p_{i} - 1|n-1$ implies $p_{i} | a^{n-1} - 1$ if we know that $p_{i} | a^{p_{i}-1} -1$. could anyone explain this for me please ?...
0
votes
2answers
29 views

A discrepancy in understanding the proof that any Carmichael number is square free.

The proof as given in " David M. Burton " is as follows: Suppose that $a^n \equiv a \pmod n$ for every integer a, but $k^2\mid n$ for some $k > 1.$ If we let $a = k,$ then $k^{n} \equiv k \pmod n.$...
0
votes
3answers
32 views

how can I prove the set $A=\{4k+1: k \in \mathbb Z\}$ is equal to set $B = \{4k-3: k \in \mathbb Z\}$

I want to know how I can approach this problem. I know I have to show A and B are subsets of one another by picking an arbitrary element x from one set and show its a member of the other set, but idk ...
0
votes
4answers
41 views

A discrepancy in the proof that 561 is Carmichael number.

The proof is given below: But I do not understand the statement in the line before last which says "These give rise to the single congruence $a ^{560} \equiv 1 \pmod n$ where gcd(a, 561) = 1 ", I do ...
1
vote
1answer
42 views

Irreducible polynomials for that each output is divisible by an integer n

Feel free to delete this question if it has been asked somewhere else before. I've recently stumbled upon this question on the Mathematics StackExchange and I've wondered how the polynomials for ...
0
votes
0answers
26 views

Modulo division by a prime [on hold]

UMAC includes a polynomial hash, which includes this operation: y = (k * y + m) mod p p is the largest prime which is less ...
0
votes
2answers
19 views

Simplifying the modulus of a linear congruences

I have seen the rule that if $\gcd(k,m) =1 $ and we have $ka \equiv kb \pmod{m}$ then $a \equiv b \pmod{m}$. But I have just seen that $3(7k) \equiv 3 \pmod{15} \implies 2k \equiv 1 \pmod{5}$ What ...
0
votes
0answers
21 views

Multiplicative order and powers

Let's consider two number $a$ and $b$ such as $gcd(a,b)=1$. Can you explain me intuitively why there exist $n>0$ such as $a^{n} \equiv 1 \space (mod \space b)$ ?
-1
votes
0answers
31 views

necessary and sufficient conditions that a number being prime or prime of special form? [on hold]

I like to gather some statements about the properties of prime numbers or prime of the specific forms. For instance 1) A prime number is a whole number greater than 1 whose only factors are 1 and ...
1
vote
0answers
73 views

Primes that divide integers of the form $n^2+1$ or $n^2+3$ [on hold]

A similar question is supposedly included in an open assignment so I have retracted my working.
1
vote
1answer
41 views

Proving that every non-zero prime element can be written as a power of g

Let $p\geq 2$ be a prime and let g be an element of order $p-1$ in $\Bbb Z_p$. Prove that every non-zero element of $\Bbb Z_p$ can be written as a power of $g$. So i wanted to start this proof by ...
1
vote
1answer
36 views

Congruence of integers and primitive roots

Lemma: In $\mathbb{Z}$, if $l\ge 1$, $p$ any prime, and $x\equiv y\pmod{p^l}$ then $x^p\equiv y^p\pmod{p^{l+1}}$. The proof is by Binomial theorem. Assume the Lemma. Suppose $x^{p^l}\equiv 1\pmod{...
2
votes
2answers
63 views

Remainder of $(1\cdot2\cdots102)^3$ modulo $105?$

I am having trouble in finding the remainder of $(1\cdot2\cdots102)^3\mod 105$ It is not possible to apply Wilson's Theorem here because 105 is composite. Can anybody help me?
0
votes
3answers
35 views

Multiplicative order when gcd=1

If $a^{n}\equiv 1 \pmod m$, then $aa^{n-1}\equiv 1 \pmod m$, so $a^{n-1}$ is the multiplicative inverse of $a$ modulo $m$ and $\gcd(a,m)=1$. What I don't understand is why $\gcd(a,m)=1$ and $a^{n}\...
1
vote
2answers
46 views

Count number of roots of polynomial modulo prime power

I found this problem in a number theory course, I am assuming (but not sure) it is supposed to be an application of Hensel's lemma. For every $n \in \mathbb{N}_0$, determine the number of solutions ...
1
vote
0answers
50 views

Math game problem, not able to understand why the solution works?

Players A and B Rules of the game: The game is played with two piles of matches. Initially, the first pile contains N matches and the second one contains M matches. The players alternate turns; A ...
0
votes
0answers
71 views

Plotting points of the form $(-p \mod(n),0)$ and $(p,0)$

Imagine taking an interval $[-n,n]$ of the $x$-axis, cutting it in half at $x=0,$ and gluing the sides over top of each other. This process is equivalent to thinking about points of the form: $(-x \...
2
votes
1answer
14 views

A difference in a formula of theorem 4.2(e) on congruence relations.

The statement of the theorem said : If $a \equiv b \pmod n$ then $ac \equiv bc \pmod n$. But I have seen it in other place as: $a \equiv b \pmod n$ then $ac \equiv bc \pmod {nc}$. Are they ...
0
votes
0answers
33 views

Finding small solutions to modular congruences

I was wondering what computational/algorithmic techniques can be used to solve a modular congruence when we are looking for a pair of small values. The specific problem is like this (the numbers are ...
1
vote
2answers
23 views

Divisibility of number $s\perp 10$

I found a property that for $s\perp 10$ we can say that there exists such $k$ that $$ 10^k \equiv 1 \pmod s $$ but I cannot prove it. Can you help me in this task. My approach: When $s\perp 10$ then ...
1
vote
1answer
32 views

time the pseudo random generator gonna start repeating itself

as you know the general formula for pseudo random generator is this U(n)=a*U(n−1)+b [mod z] where we have control of U(n-1)...
3
votes
2answers
85 views

If $a^{m}+1|a^{n}+1$ then prove that m|n.

Actually I know a similar proof which is, $a^{m}-1|a^{n}-1 \iff a|n$ But I can't prove this. I also need some examples of the question. Can't seem to find any correlation between the two proofs. I ...
0
votes
0answers
44 views

Computing modular inverses $65537^{-1\!}\bmod (10^n\!-1)$ for large $n$

I have the following formula: $$d \cdot 65537 \equiv 1 \pmod{9999...}$$ I have to find $d$, even in case the modulo is 30 digits long. This means I am not supposed to brute force it, but I haven't ...
0
votes
0answers
19 views

How to algebraically mirror a finite subset of integers? [closed]

Let's take the set $S=\{0,1,...8,,9\}$ as an example. By mirroring I mean creating a function $f$ such that $f(x) = x$ is $x \in \{0, 4\}$ and $f(x) = 4 -(x \equiv 5)$ otherwise. The above however ...
1
vote
1answer
57 views

Knowing that $a+b\equiv 1 \pmod{7^{n+1}}$ show that $a^7+b^7\equiv 1 \pmod{7^{n+2}}$

Knowing that $a,b$ are prime integers and $a+b\equiv 1 \pmod{7^{n+1}}$ show that $a^7+b^7\equiv 1 \pmod{7^{n+2}}$ I used $a^7+b^7=(a+b)(a^6-a^5b+a^4b^2-a^3b^3+a^2b^4-ab^5+b^6)$ and tried to show that ...
1
vote
0answers
32 views

Finding the modular of a Square Root of a product of many numbers

I am working on Quadratic Sieve and at some stage I need to find $$ \sqrt{\prod_{k=1}^n y_k} \pmod{N} $$ Now the Product (inside square root) getting bigger and bigger (up to few hundred numbers) and ...
1
vote
1answer
28 views

Assumptions in Artin's primitive root conjecture

I'm having a little trouble, understanding the necessity of the assumptions in Artin's Conjecture. Artin's primitive root conjecture states, that: for any $$a\in \mathbb{Z}\setminus \{-1\}$$ and $$...
1
vote
3answers
61 views

Primes number $n,n+2,n+6,n+8,n+12,n+14$

Find all natural number $n$ such that all the following numbers are primes : $$n,\;\; n+2,\;\;n+6,\;\;n+8,\;\;n+12,\;\;n+14$$ are all prime numbers
0
votes
2answers
29 views

Modulo multiplicative inverse

In ax $\equiv$ 1 (mod m) , when gcd(a, m) = 1, there is exactly one solution, i.e., when it exists, a modular multiplicative inverse is unique. This is written in wikipedia. I am confused ...
2
votes
4answers
101 views

Find the least whole number only consisting of the digit 1 such that it is divisible by 3333…3.(100 3's)

Find the least whole number only consisting of the digit 1 such that it is divisible by 3333...3.(100 3's). My approach: we see that 111 is divisible by 3. Hence 100 3's would divide 300 1's. Is my ...
0
votes
1answer
22 views

-1 as a Quadratic Residue mod $p$ $\Rightarrow$ $p \equiv_4 1$ [duplicate]

Suppose $p$ is odd prime. If $x^2 \equiv_p -1$, show $(x^2)^{\frac{p-1}{2}} \equiv_p 1$, and conclude that $p \equiv_4 1$ ( I cannot get to this part for some stupid reason) Here is what I have, ...
1
vote
2answers
41 views

If $a \equiv 9 \pmod {12}$, find all possible values for $\gcd(a^2+21a+72,252)$

We know that $$a^2+21a+72 \equiv 9^2 + 21 \cdot 9 + 0 \equiv 6 \pmod {12}$$ So we know that that expression, let's say $\alpha$, is such that $12 \mid \alpha - 6$. But then $12 \mid 2(\alpha - 6)=2a+...
0
votes
1answer
68 views

Is there a specific theorem or name for this particular fact about primes? (Mod 6)

Is there a particular theorem or name defining the property/behavior of primes such that all primes (greater than 3) are congruent to 1 or 5 (mod 6)? I could have sworn I saw one years ago, but I ...
0
votes
2answers
109 views

Can we construct a multiple of any number by repeating another arbitrary number twice?

Extension of this question: given a desired integer (non-necessarily prime) factor $f$, can we solve for some $n$ such that any arbitrary $n$ digit number repeated twice is a multiple of $f$? ...
2
votes
3answers
80 views

Prove that $2^{2^{2^{\cdot^{\cdot^{2}}}}} \mod 9 = 7$

Prove that $\underbrace{2^{2^{2^{\cdot^{\cdot^{2}}}}}}_{2016 \mbox{ times}} \mod 9 = 7$ I think that it can be done by induction: Base: $2^{2^{2^{2}}} \equiv 2^{16} \equiv 2^8 \cdot 2^8 \equiv 2^...
1
vote
2answers
47 views

$a \equiv b \mod k \implies a \equiv ? \mod k^2$?

Is there any modular law such that: $a \equiv b \mod k \implies a \equiv ? \mod k^2$ I know that $$ a \equiv b \mod k \implies a^n \equiv b^n \mod k $$ but sometimes I need to power only $k$ and ...
2
votes
1answer
65 views

Congruence equation with power solving method

How can the equation like $$ x^{118}\equiv 113\;\; (mod\; 1001) $$ if I know the Fermat's little theorem, Chinese remainder theorem, Euler's theorem and basic operations on congruence? My approach: ...
1
vote
1answer
39 views

Modulo congruences and remainder

Let $x \in \mathbb{Z}$ Show that if $N\mid M$ then $(x\pmod M)\pmod N = x \pmod N$ My proof: Assume $x \in \mathbb{Z}$ is arbitrary. Then define $x\pmod M =r \iff x \equiv r\pmod M$ where $0\leq r &...
0
votes
1answer
39 views

Modular aritmetic and fields

I'm studying the concept of field applied to modular aritmetic. Is it correct to say that, if the dimension is a prime number $p$ then field properties are satisfied for the integers $\bmod p$ ? And ...
1
vote
1answer
37 views

Why is it that only exponents that are divisors of φ(N) capable of generating the identity element as a power when N is prime?

Let $p=x$ where $a^x \equiv 1\pmod N$. When $N$ is prime I can check whether $p=N-1$ and if it is, there are a full set of remainders. However, if $p<N-1$, I need to keep checking. For example, if $...
1
vote
1answer
37 views

Use congruence to show that the output of a natural number function is always divisible by 6 [duplicate]

I have been asked to show that for any natural number $n$, $(7n+30)(13n+7)(n+2)$ is divisible by 6. I can show that this function is congruent to $n(n+1)(n+2)$. I noticed that this function is the ...