Tagged Questions

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

learn more… | top users | synonyms

0
votes
1answer
20 views

Solutions of $a^{2} - 2b^{2} \equiv 0$ mod $p$

I came across this question in attempting to find $p$ for which $\mathbb{Z}_{p}[\sqrt{2}]$ is a field. Consider the equation: $$a^2 - 2b^2 \equiv 0 \enspace \text{mod p}$$ For which primes $p$ is ...
-1
votes
1answer
31 views

Show that x = (66B − 65a) mod 143.

For each natural number $m$ we define $J_m = \{0, 1, . . . , m − 1\}$, the set of all possible residues modulo $m$. Let $x \in J_{143}$. Define $a \equiv x \pmod{11}$, $B \equiv x \pmod{13}$ Show ...
0
votes
2answers
25 views

If $a \equiv b \bmod n$, then $\gcd(a, n)= \gcd(b,n)$ [duplicate]

Again, I have been stuck in a problem of modular arithmetic. Given that $a,b, n \in \mathbb Z $ and $n>0$ and $a \equiv b \bmod n$. Show that $\gcd(a, n)= \gcd(b,n)$.
0
votes
1answer
16 views

proof of a property of modular arithmetic

I have been stuck in a problem related to modular arithmetic. I have tried it using the generalized Euler's formula for $\gcd(a,b)=as+bt$, but have not reached the proof so far. The question is: ...
1
vote
2answers
19 views

Modular arithmetic with (mod 20)

Got a question on my midterm in discrete mathematics and I can' figure out how to approach it: $19^{3701}+1 \equiv 0\ (\textrm{mod}\ 20)$ I was thinking about Fermat´s little theorem, but the 20 is ...
4
votes
2answers
769 views

Why is $20 ≡ 2 \pmod 6\;?$

Could anyone explain to me why $20 ≡ -22 \pmod 6\;?$ At school we did the following method to find $-x \mod n$ by doing: x mod n (in this case ...
0
votes
2answers
16 views

Modulo congruence

I have a problem here that I have no idea how to go about solving. It states: Let $n∈Z$ with $n>1$. (a) If $n=2k$ for some odd integer $k$, prove that $k^3≡k \pmod{2n}$. (b) If $n=2k$ for ...
0
votes
0answers
11 views

Finding set of integer pairs for which two integer polynomials intersect

I am wondering if there is a theorem in number theory that addresses the following issue: Suppose we have two polynomials, f and g, with integer coefficients. Is there a general way to find elements ...
-1
votes
1answer
22 views

Show that a·c ≡ b·c (mod m) with a, b, c and m integers with m≥2 does not [3] imply a ≡ b (mod m) [on hold]

I'm working through some practice problems but I am having some trouble understanding this question and was wondering if it'd be possible for someone to help me go over it step by step. Thanks
0
votes
1answer
33 views

Why is the discrete logarithm problem in $(\mathbb{Z}_n,+)$ easy?

I have trouble understanding why the discrete logarithm problem in $(\mathbb{Z}_n,+)$ should be easy: I tried it with the following example: $$a \cdot b \equiv y \pmod {p}$$ If $a=11, b=2$ and ...
2
votes
0answers
20 views

Arithmetic background of this RNG code

I am trying to figure out the mathematical background of the random number generation of an old video game. It does iterations where it updates a 33-bit state consisting of the variables z (32-bit) ...
0
votes
1answer
12 views

Linear Congruences Examples

Solve the following linear congruences: (i) $23x \equiv 16$ mod $107$ (ii) $234x \equiv 20$ mod $366$ (iii) $234x \equiv 6$ mod $366$. I am trying to solve these through the use of the ...
0
votes
0answers
38 views

Prove $2^n \not\equiv 1 \pmod{n}$ for $n>1$ [duplicate]

Prove that $2^n \not\equiv 1 \pmod{n}$ for $n>1$. I'm asking for any advice.
0
votes
0answers
18 views

Modulo-2 arithmetic division

I been recently studying modulo 2 arithmetic addition, subtraction and division. I fully understand addition and subtraction, but I'm still not clear about division. I've made the following ...
1
vote
1answer
21 views

Modular exponentiation twice over

What is a general way to calculate something like $2147089412^{1147068432^{647017654}}$ mod m? It looks like modular exponentiation, but how do you reduce the highest part properly? Note: $m$ is ...
0
votes
0answers
9 views

Let p be a prime number and let n ≥ 1. Show that $\mathbb{F}_p$ contains an element of order n iff p ≡ 1(mod n).

Let p be a prime number and let n ≥ 1. Show that $\mathbb{F}_p$ contains an element of order n iff p ≡ 1(mod n). For the reverse direction, assume $p \equiv 1(mod n). \text{Let } g \in \mathbb{F}_p ...
4
votes
2answers
22 views

$x^2$ $\equiv$ $1$ $\mod{p}$

Can someone provide the proof that $x^2$ $\equiv$ $1$ $\mod{p}$ iff $x\equiv1 \mod{p}$ or $x\equiv p-1 \mod{p}$, where $p$ is a prime? The argument I have in mind is setting up a bijection, like in ...
-3
votes
2answers
26 views

Show that $a c\equiv b c\pmod m,\;a. b, c, m \in \mathbb Z$ and $m \geq 2 $ does not imply $a\equiv b \pmod m$ [on hold]

Show that $a c\equiv b c\pmod m$ with $a. b, c, m \in \mathbb Z$ and $m \geq 2 $ does not imply $a\equiv b \pmod m.$
1
vote
1answer
26 views

Solve the following congruence for x (Modulo Question)

I need help in a question that I'm having a hard time understanding... It is asking to determine the congruence for $x$ and expressing the answer in the range 0-1000: $$ 200 . x = 13 \pmod{1001} $$ ...
0
votes
0answers
13 views

Is there any convention regarding the order of operation of the binary modulo operator?

Is there any predominant convention as to where the binary modulo operator (i.e., the variant of the modulo operator that is not applied to a whole equation) ranks in the order of operations, in ...
1
vote
3answers
39 views

Is modular arithmetic defined for all rational numbers (with denominators coprime to modulus)?

In the expression $\frac{1}{b}\pmod m$, where $(b,m)=1$, is $\frac{1}{b}$: a) a rational number (and so rational numbers are defined in modulo arithmetic using multiplicative inverses)? b) just ...
1
vote
0answers
22 views

Computation of large powers

How do I check if $2^{123456789}$ is divisible by 9? I tried using modular exponentiation but it is way too tedious. Is there an easier or faster way to solve it? Thanks!
1
vote
1answer
29 views

Primitive roots for a number

I want to show if a number a is a primitive root$\pmod{n}$ Is there a way to show this without raising a to all the powers between 1 and n-1?
1
vote
1answer
15 views

Internal and Direct Product question, need help with explanation

I am asked to express a group G={1,7,17,23,49,55,65,71} under multiplication modulo 96 as an external and internal direct product of cyclic groups. However I also have an example to help with it, but ...
2
votes
2answers
43 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
1
vote
0answers
23 views

Chinese Remainder Problem with three equations

Let's consider: $$*\begin{cases} 7x \equiv 2 \mod 5\\ 3x \equiv 2 \mod 4 \\ 5x \equiv 2 \mod 6 \end{cases}$$
1
vote
2answers
32 views

Principal Square Root mod

"Theorem: let p be a prime satisfying $p=3\bmod4$. Then for an integer y which is a square modulo p, $x=y^{(p+1)/4}\bmod p$ is a square root mod p of y. That is, $x^2=y\bmod p$. This is called the ...
0
votes
0answers
22 views

Strong pseudoprime base b

Show that the composite number 1281 is a strong pseudoprime base 41. "$n-1=2^rm$, then n is a strong pseudoprime base b if either $b^m=1modn$ or $b^{2^sm}=-1modn$" Ok so I have $n=1281$ and $b=41$ ...
0
votes
3answers
29 views

Modular equations: where did I make a mistake?

I want to solve the simultaneous congruences $$\begin{cases} 2x \equiv 4 \mod 8 \\ x \equiv 2 \mod 6 \end{cases} $$ My solution: $$2x \equiv 4 \mod 8 \iff x = 4l + 2 $$ $$x \equiv 2 \mod 6 \iff 4l + ...
0
votes
4answers
33 views

Modular arithmetic, very simple implications.

$$3t \equiv 1 \mod 4 \Rightarrow t \equiv 3 \mod 4 $$ I don't understand that, so I'm asking for explain me. Thank, in advance, greetings.
0
votes
3answers
32 views

Finding divisibility of a number using modular arithmetic

Let N = 12345678910111213141516171819. How can I use modular arithmetic to show that N is (or isn't) divisible by 11? In general, how can I apply modular arithmetic to determine the divisibility of an ...
0
votes
2answers
21 views

Question about modular arithmetic notation

In this document: http://cims.nyu.edu/~kiryl/teaching/aa/les092603.pdf The ordered pair notation is used but it is never explained what it means. ex: ...
0
votes
1answer
45 views

Proof, that $a \equiv 1 \pmod{p}$

Let $n \in \mathbb{N}^{+} \smallsetminus \{{1}\}$ and $p = min\{p \in \mathbb{P} : p \mid n\}$. Also, let $a \in \mathbb{Z}$ and $a^n \equiv 1 \pmod{n}$ I need to proof, that $a \equiv 1 \pmod{p}$. ...
0
votes
1answer
48 views

How to show a number is not a sum of squares

I've been tasked with the following: Let $m$ and $n$ be positive integers, prove that $4^{n}(8m+7)$ cannot be written as the sum of three squares. I've already gotten the idea that I should do ...
1
vote
1answer
32 views

Modular arithmetic and using in well-ordering principle

I need to prove the following, but I do not know how to go about it. If $$ (*)\:\:\: x^{3} - y^{3}= 3^{n} $$ Then $$ x \equiv 0 (mod 3) \:\: and \:\:\: y \equiv 0 (mod 3)$$ In addition, ...
-1
votes
2answers
57 views

Units in the ring $\mathbb{Z}(\omega)$

If $\omega \not= 1$ is a cube root of unity in $\mathbb{C}$, show that the units in the ring $\mathbb{Z}[\omega]$ are the elements of modulus 1. Hence, or otherwise, show that $U(\mathbb{Z}[\omega]$ ...
2
votes
1answer
36 views

computing $29^{25}$ (mod 11)

I'm trying to learn how to use Fermat's Little Theorem. $29=2\cdot11+7 \Rightarrow 11\nmid29$ by the theorem we have $29^{10}\equiv 1$(mod 11) $25=10\cdot 2 + 5$ $ ...
0
votes
1answer
15 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
-2
votes
1answer
27 views

What is the most efficient way to evalaute the function $f(N, R) = F(N)/(F(N-R)*F(R))$ where $F(N) = 1^1*2^2*…*N^N$? [on hold]

In particular goal is to find $f(n,r)\mod(m)$ for given values of n, r, m and m is a prime number. $f(n,r) = F(n)/(F(n-r) * F(r))$ where F(n) = $1^1 * 2^2 * 3^{3} *... * N^N $ Here is the python ...
2
votes
0answers
40 views

Compute digits of a number.

The question is what the last $10$ decimal digits of $2^{3^{4^{5^{6^{7^{8^9}}}}}}$ are? I do not get the following solution and its motivation. I would appreciate if someone would shed light on it. ...
0
votes
0answers
12 views

Pari/ GP Mod function

I am fairly new to using Pari/GP. Trying to compute below formula: y1=Mod((g^a1)*(y^a2),p); When I try to output y1, instead of giving me the value of Mod ...
3
votes
1answer
57 views

Congruence for the sums of odd powers of integers [duplicate]

Does someone know how to prove ***EDIT by induction**** that for all integers $n\ge1$, $k\gt0$ $$\sum\limits_{i=1}^{n} {i^{2k+1}}\equiv 0\ \ \ \pmod{\frac{n(n+1)}{2}}$$ I thought this should be a ...
-1
votes
0answers
13 views

Assuming a natural number $m>50$, how many values of $m$ exist so that it divides $n^{n+1} + 1$ [closed]

Assuming a natural number $m>50$, how many values of $m$ exist so that it divides $n^{n+1} + 1$ where $n\ge0$ ($n$ is also natural)
0
votes
2answers
29 views

Prove divisibility

We have the following proposition: $$P(n): 13^n+7^n-2\vdots 6$$. Prove $P(n)$ in two ways. I know that one of them is mathematical induction. I don't know many things about the other one, I know ...
0
votes
2answers
17 views

Inverse of $3$ in $\mathbb{Z}_7$ using Fermat's Theorem or its corollaries.

What is $3^{-1}$ , the multiplicative inverse of $3$ in $\mathbb{Z}_7$. Use Fermat's Theorem or its collaries. How do I make use of the Fermat's theorem to solve this? I know how to solve it using ...
0
votes
0answers
13 views

Find $R[r] \mod M $ where R is a recurrence relation and M can be any integer?

Let N,M are two constant integers and they may or not be prime . A recurrence relation R is defined as using N $R[1]=1$ , $R[r]=\frac{R[r-1]\space * \space p}{r^r}$ , where $p = {(N-r+1)}^{(N-r+1)}$ ...
2
votes
3answers
59 views

Given that a and b are integers, a ≡ 4 (mod 13), and b ≡ 9 (mod 13). Find c where c ≡ 9a (mod 13).

The Problem I had my first exposure to number theory today. Trying to work on some problems in hope that it will start to make more sense. Here is the problem (part a) I'm stuck on right now. My ...
6
votes
0answers
53 views

Remainders of Fibonacci numbers

Let $a>b$ be positive integers. Is there a Fibonacci number that is $b$ modulo $a$? We know that the Fibonacci numbers are periodic modulo $a$. Indeed, consider pairs $(F_i,F_{i+1})$ modulo $a$. ...
1
vote
1answer
37 views

Breaking RSA Ciphertext

Sam and Tim have set up their RSA keys $(e_s, n), (e_t, n),$ respectively, where the n-value is the same. Furthermore, it happens that $\gcd (e_s, e_t) = 1$. Suppose that their friend Rob wants to ...
1
vote
1answer
49 views

Relation between $(a\bmod b)\bmod c$ and $a\bmod c$

Will (a%b)%c be equivalent to a%c? Given $b>c$ and $b$ is a prime number? If not is there any other equality that will hold? ...