Tagged Questions
0
votes
0answers
15 views
When is it solvable:$10^a+10^b\equiv -1 \pmod p$
If $p$ is a prime, $(a,p)=1$,denote $ord(a,p)=d,$ where $d$ is the smallest positive integer solution to the equation $a^d\equiv 1 \pmod p$.We can prove that $$10^n\equiv -1 \pmod p\tag1$$ is ...
1
vote
1answer
25 views
Modulus Cancellation Law
I'm trying to understand the proof for cancellation law in modulus which states that:
...
3
votes
2answers
44 views
Finding inverse modulo
I'm trying to find "the smallest positive multiple of 100" that leaves remainder 9 when divided by 19.
Here is what I have done before I got stuck:
1) x ≡ 9 mod 19
2) gcd(9,19) = gcd(19,9)
19 ...
1
vote
0answers
35 views
Revised: Primes of form $p \equiv m \in S \mod x \ $
Refer to this question for background.
I was speculating if there was an elegant way to define sequences
A007645,A002313,A045357,A045407,A042986,A045331,
A045425,A045374,A045400,A045350,A042988;
...
4
votes
3answers
321 views
The last 2 digits of $7^{7^{7^7}}$
What is the calculation way to find out the last $2$ digits of $7^{7^{7^7}}$? WolframAlpha shows $...43$.
-2
votes
2answers
59 views
Use the modular exponentiation algorithm to find $13^{277} \pmod {645}$
I need to solve this question using the modular exponentiation method.
3
votes
1answer
33 views
$\mathbb{Z}/m\mathbb{Z}$: A Complete Set of Representatives
So, I'm letting ${\scr{A}}=\{a_1,\dots,a_n\}$ be a complete set of representatives (C.S.R.) for $\mathbb{Z}/m\mathbb{Z}$. I'm considering all $b\in \mathbb{Z}$ and seeing if ${\scr{B}}=\{a_1+b, a_2+b, ...
1
vote
4answers
59 views
$[4]_{17}[x]_{17} = [2]_{17}$: How to optimally solve this equality.
This notation is found in Concrete Introduction to Higher Algebra.
Here is my method:
For something like $[3]_{11}[x]_{11}^2=[4]_{11}$ I've just been using C++ code like this:
...
3
votes
1answer
63 views
How do you calculate $25^{11} \pmod{341}$?
How do you calculate $25^{11} \pmod{341}$?
I understand you have to split the exponent into $11 = 1 + 2 + 8$?
3
votes
3answers
43 views
Solving for Modular arithmetic
Solve the equation $38z\equiv 21 \pmod {71}$ for z.
Little confused by the questions. My attempt is: $38 \odot z = 21.$ Then find the inverse of 38 from mod 71 and multiply both sides. Lastly, take ...
5
votes
2answers
164 views
Does there always exist an odd number of elements?
Given a nonzero integer $k$, does there always exist a positive integer $n$ such that there are exactly an odd number of elements $i\in\{0,1,...,n-1\}$ with $\frac{2^n-1}4 < 2^ik \mod{2^n-1} < ...
1
vote
1answer
53 views
Does $a \mid bc$ imply $\frac{a}{(a,b)} \mid c$?
If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
-1
votes
5answers
69 views
$(a,m) = (b,m) = 1 \overset{?}{\implies} (ab,m) = 1$
In words, is this saying that since $a$ shares no common prime factors with $m$ and $b$ shares no common prime factors with $m$ too, then of course the product of $a$ and $b$ wouldn't either!?
3
votes
6answers
95 views
$11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$
Problem
So, I am to show that $11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$.
Attempt
This is a useful proposition given by the book:
Proposition 12. $11$ divides a ...
-2
votes
1answer
64 views
Finding a primitive root modulo $13$ [duplicate]
Find a primitive root modulo each of the following integers.
a) $13$
My TA said we are not going to go over this. We did not go over the topic. It seems like something good to know though.
...
1
vote
2answers
34 views
Determine number of squares in progressively decreasing size that can be carved out of a rectangle
How many squares in progressively decreasing size can be created from a rectangle of dimension $a\;X\;b$
For example, consider a rectangle of dimension $3\;X\;8$
As you can see, the biggest square ...
1
vote
1answer
68 views
Finding a primitive root modulo $11^2$
Find a primitive root modulo each of the following moduli:
a) $11^2$
My TA said he is not going to go over this so do not worry about it. He said you can try this if you want but he would ...
2
votes
6answers
97 views
Finding the remainder when $2^{100}+3^{100}+4^{100}+5^{100}$ is divided by $7$
Find the remainder when $2^{100}+3^{100}+4^{100}+5^{100}$ is divided by $7$.
Please brief about the concept behind this to solve such problems. Thanks.
-4
votes
1answer
41 views
least non-negative residue of $a^{67}$ modulo $7$
My professor might accept C++ code to show that for $0 ≤ a ≤ 6$, the least non-negative residue of $a^{67}$ modulo $7$ is $a$.
0
votes
1answer
24 views
Is the “least non-negative residue” of $b^p \pmod{m}$ just $b^p \pmod{m}$?
I'm just wondering if the "least non-negative residue" of $b^p \pmod{m}$ is just $b^p \pmod{m}$ itself. What is the "least non-negative residue"? How is it found? Is this how it is found? Just by ...
-2
votes
1answer
31 views
Modular Arithmetic: Least Non-negative Residues
I am to compute the least non-negative residue of $4^n \pmod{9}$ for $n = 1, 2, 3, 4, 5, \dots$
I must also prove that $6 · 4^n ≡ 6 \pmod{9}$ for every $n > 0$.
0
votes
4answers
126 views
Calculations by Hand
Find the least non-negative residue of:
(i) $5^{18}$ mod $11$
(ii) $68^{105}$ mod $7$
(iii) $4^{47}$ mod $12$
(iv) $66^{75}$ mod $19$
C++ code failed... I'm trying to do by hand now. Maple has ...
2
votes
1answer
30 views
$15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$
For which numbers $a$ is it true that if $15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$?
I know that this means that $a\frac{15-c}{25}=k_1\in \mathbb{Z}$ and $\frac{15-c}{25}=k_2\in \mathbb{Z}$, but ...
2
votes
2answers
32 views
Help with proof of showing idempotents in set of Integers Modulo a prime power are $0$ and $1$
I was reading online for a project I'm currently doing and came across the following claim and proof. The statement would be useful to me, and although I've spent a long time looking at it there's ...
2
votes
5answers
94 views
How to show that $p!+1\equiv 1 \mod k$
I am a non mathematician who is taking a self study class in number theory. I was wondering how to formally prove the following:
Let $p$ be a prime number. How can I show that $$p!+1\equiv 1 \mod k$$ ...
3
votes
2answers
65 views
Is $\sum\limits^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}$?
Let $n$ be a positive integer such that $n+1$ is a prime power. That is, to illustrate $n+1$ is $9$ or $25$. Prove that
$$\sum^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}.$$
Hint: I ...
3
votes
6answers
45 views
Large modular exponent arithmetic
How would you compute $10^{221}$ mod $13$ by repeated squaring? I just started studying discrete mathematics and I think this would help me in the future. I looked at this example Computing large ...
1
vote
3answers
63 views
Computing large modular numbers
How do you compute large modular arithmetic such as $8^{128}$ $mod$ $100$ or $10^{111}$ $mod$ $137$ or $3^{100}$ mod $17$? I know that one way is repeated squaring. For the first one, my book says 16, ...
4
votes
2answers
46 views
Modular Exponentiation
Give numbers $x,y,z$ such that $y \equiv z \pmod{5}$ but $x^y \not\equiv x^z \pmod{5}$
I'm just learning modular arithmetic and this questions has me puzzled. Any help with explanation would be ...
1
vote
4answers
85 views
Finding the last digit in a large exponent.
I'm practicing for my algebra exam but I stumbled on a question I don't know how to solve.
Let N = 3^729. What is the last digit of N?
The example answer says Since gcd(3, 10) = 1, check that
3^4 = ...
3
votes
1answer
77 views
Using Fermats Little Theorem to show $2^{17} -1$ is prime
Show that $n = 2^{17} - 1$ is prime by using Fermat's Little Theorem $2^{p-1} \equiv 1 \mod p$ for any $p$ dividing $n$.
I said, that by FLT, we get $2^{16} \equiv 1 \mod 17$, and we can see that ...
0
votes
1answer
53 views
Number Theory Proof Need Logic Checked
I'm working on the following problem:
Show that if $x^{p} + y^{p} = z^{p}$, then $p \space | \space (x + y -z)$
So far my proof looks something like this:
Suppose $p \nmid \space (x+y-z)$ ...
2
votes
1answer
56 views
Prove the converse of Wilson's Theorem
... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime.
This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
3
votes
3answers
116 views
The Chinese Remainder Theorem
I'm trying to do some questions on the Chinese Remainder Theorem, I've being reading the Wikipedia explanation but I still don't get it. Can someone explain it to me, please?
Here is the question I'm ...
4
votes
3answers
133 views
Show that there exists $f ∈ \mathbb{Z}$ such that $f^2 + f +1 ≡ 0 \pmod p$.
Let $p ≡ 1 \pmod 3$ be a prime. Show that there exists $f \in \mathbb{Z}$ such that $f^2 + f +1 \equiv 0 \pmod p$.
I know the first few primes of this form are: $7,13,19$
So for example $p=7$ we ...
0
votes
2answers
36 views
Trying to prove $A=\{2, 4, 8,…,2^k\}$ is closed under multiplication in $\mathbb{Z}/(2^{k+1}-2)\mathbb{Z}$
I've been investigating as part of a project the structure of integers modulo $n$ ($\mathbb{Z}$/n$\mathbb{Z}$) under multiplication. One aspect I'm looking at is, for any natural number $k$, finding a ...
1
vote
1answer
41 views
Solving for x in a mod relation? [duplicate]
How do I approach the problem: $$7^{95} \equiv x^3\text{(mod 10)}$$ when solving for $x$?
9
votes
1answer
158 views
Elementary Number Theory; prove existence
Prove that there exists a positive integer $n$ such that
$$2^{2012}\;|\;n^n+2011.$$
I was wondering if you could prove this somehow with induction (assume that $n$ exists for $2^k|n^n+2011$ ...
0
votes
0answers
43 views
Modulus question [duplicate]
Hey i am studying for my exam and I was wondering how to solve $2023^{2297}\equiv x \pmod{3953}$. The example just says it is $20 \bmod{3953}$ but I am unable to arrive at this answer. Thanks so much ...
1
vote
2answers
59 views
Chinese remainder theorem example help
I am currently studying for my upcoming algebra exam and I was wondering if anybody could explain to me this example of a very basic CRT question.
If $x=38$ then $x \equiv 2 \pmod{9}$ and $x ...
9
votes
7answers
654 views
Pattern to last three digits of power of $3$?
I'm wondering if there is a pattern to the last three digits of a a power of $3$? I need to find out the last three digits of $3^{27}$, without a calculator.
I've tried to find a pattern but can not ...
1
vote
3answers
62 views
Basic Modulo Question
I've been having trouble with this example while studying for my exams. Why is
$$2023^{2297}\equiv 20 \pmod{3953}\;?$$
Thanks so much for any help I can get!
The examples solves the answer by ...
2
votes
1answer
47 views
How to compose given add, sub, mult, div functions to map an integer M to N?
Given six integers ($M$, $N$, $a$, $b$, $c$, $d$), is it possible to create a function $H$ such that $H(M) = N$, with the restriction that $H$ is a composition of the following four functions (which ...
1
vote
0answers
49 views
Legendre Symbol, find the value of $\frac{p}{q}$ for all combinations
Legendre Symbol, find the value of $\frac{p}{q}$ for all combinations of $p=7,11,13$ and $q=227$
My thought:
$(7, 227)$ are distint odd primes, same for $(11,227)$ and $(13, 227)$
thus, ...
3
votes
4answers
73 views
How to derive this expression $ r ^{ (p-1)/2} \equiv -1 \pmod p$ for primitive root of an odd prime $p$.
While studying Elementary Number theory by David M. Burton I came across this line:
because $r$ is a primitive root of $p$, $$ r ^{ (p-1)/2} \equiv -1 (\mod p) $$ where $p$ is an odd prime.
...
3
votes
4answers
128 views
Prove that $2222^{5555}+5555^{2222}=3333^{5555}+4444^{2222} \pmod 7$
I am utterly new to modular arithmetic and I am having trouble with this proof.
$$2222^{5555}+5555^{2222}=3333^{5555}+4444^{2222} \pmod 7$$
It's because $2+5=3+4=7$, but it's not so clear for me ...
5
votes
2answers
130 views
How many solutions does $x^2 \equiv {-1} \pmod {365}$ have?
How many solutions does $x^2 \equiv {-1} \pmod {365}$ have?
My thought:
$365 = 5 \times 73$ where $5$ and $73$ are prime numbers.
So we can obtain $x^2 \equiv {-1} \pmod 5$ and $x^2 \equiv ...
4
votes
6answers
94 views
Solve $91x\equiv 84\pmod{147}$
So, I posted a similar question to this, and I know that the equation is solvable because $\gcd(91,147) = 7$ and $7 \mid 84$.
Plugging into Wolfram Alpha, I found that the solution is a line $21n + ...
4
votes
2answers
44 views
Easy way to compute $k^{20}=1\pmod{101}$?
I know that it is assumed hard to calculate the opposite ($20^k$), basically the discrete log problem. I also know that is easy to verify for some $k$ whether $k^{20}=1\pmod{101}$ holds. Solutions are ...
0
votes
1answer
133 views
Find all solution of a Quadratic Congruence
Find all solution of $x^2 \equiv a \pmod {11^2}$, for every $a \in Q_{11}$.
I'm not sure what's the question actually asking. Do I need to find all the quadratic residues of $\pmod {11^2}$ or ...
