Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
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 ...
3
votes
1answer
74 views
Why don't I end up with the same splitting field?
I've understood that the splitting field of $x^4+2$ and the splitting field of $x^4-2$ over $\mathbb{Q}$ are both the field $\mathbb{Q}(\sqrt[4]{2} , i)$. With degree $8$ over $\mathbb{Q}$. This ...
-2
votes
1answer
32 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 ...
5
votes
1answer
58 views
For which $a$ is $n\lfloor a\rfloor+1\le \lfloor na\rfloor$ true for all sufficiently large $n$?
Inspired by this question I ask this. For which $a$ is $n\lfloor a\rfloor+1\le \lfloor na\rfloor$ true for all sufficiently large $n$?
The original question concerned $a=e$, the usual ...
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 ...
6
votes
6answers
181 views
Representing the function $\mathbb Z_9\to\mathbb Z_9$, $f(0) = 1$, $f(1) = \ldots = f(8) = 0$ as a polynomial in $\mathbb Z_9[x]$
Let $\mathbb Z_9=\left\{0,1,2,3,4,5,6,7,8\right\}$ be the set of integers modulo 9 and $f:\mathbb Z_9 \rightarrow \mathbb Z_9$ be a function.
Assume $f(0)=1$, $f(1)=f(2)=...=f(8)=0$. What is the ...
2
votes
2answers
51 views
Order of a group?
Let $a = g^{16}$. Assume $\operatorname{ord} g = 40$. Find $\operatorname{ord} a$.
Not sure how you would find $\operatorname{ord}a$. We did not go over this. Here is what I did
We know that ...
0
votes
0answers
31 views
Show that $ {\overline a }$ is an inverse of a modulo n, then $ord_n$a = $ ord_n{\overline a }$.
Show that $ {\overline a }$ is an inverse of a modulo $n$, then $\text{ord}_n$a = $ \text{ord}_n{\overline a }$.
Here is the proof I did:
That $\text{ord}_na = \text{ord}_n{\overline a }$. follows ...
0
votes
4answers
117 views
$(a,b)=d \overset{?}{\implies} (a^3,b^3)=d^3$
Why is this true? I suspect that its because $\frac{LCM(a,b)^3GCD(a,b)^3}{b^3}=a^3$ and $\frac{LCM(a,b)^3GCD(a,b)^3}{a^3}=b^3$, so it must be the case for $LCM(a,b) \notin R(a,b)$, right?
1
vote
0answers
25 views
Quadratic Equation Modulo an even composite
I am familiar with using the quadratic formula and Tonelli-Shanks with Hensel's Lifting Lemma to solve a quadratic equation, but how do I solve a quadratic equation in an even modulus? I can't use the ...
9
votes
1answer
153 views
How to find all integers $a,b > 1$ satisfying $b \mid a^2+1$ and $a^2 \mid b^3+1$?
Let $a,b\in \mathbb{Z}$ with $a,b>1$, and such that $b \mid a^2+1$ and $a^2 \mid b^3+1$. Find all such $a,b$.
I found $a=3,b=2$. Are there any other solutions? Thank you.
yesterday I have ...
6
votes
1answer
137 views
Two questions re: $\sum_{n=1}^{\infty}n^{-p_{n}}$
Edit Motivation for question: I looked up the decimal expansion of:
$$\sum _{n=1}^{\infty } \sum _{k=n}^{\infty } k^{-2 k},$$
which matches the first seven digits of the function in question. I would ...
3
votes
5answers
135 views
Revisted: GCD - $(a,c)=1=(b,c) \overset{?}{\implies} (ab,c)$
How should I show that if $(a,c)=1=(b,c)$ then $(ab,c)$?
How should I show that if $a|bc$ and $(a,b)|c$, then $a|c^2$. I think I have the answer, but I'm not sure.
1
vote
1answer
78 views
Finding integers to satisfy two inequalities.
Let $a,b,c $ be integers. We want to prove that there exists some integers $r,u,s,t$ such that $ru-st=1$ and $$|2art+b(ru+ts)+2csu|\le |ar^2+brs+cs^2|\le |at^2+btu+cu^2|$$
This problem is from: ...
0
votes
1answer
43 views
Linear Diophantine Equations: Integer Solutions $x,y$ exist for $ax+by=c$, but how do I find them by hand?
I'm trying to find which of $133x+203y=38$, $133x+203y=40$, $133x+203y=42$, and $133x+203y=44$ have integer solutions. I know that only the third equation suffices for these conditions because ...
1
vote
4answers
70 views
I cannot find the last factor of this expression?
I'm supposed to factor $x^8-y^8$ (the exponents are 8 for both if it is too difficult to see) as completely as possible. It is easy to factor this to $(x+y)(x-y)(x^2+y^2)(x^4+y^4)$. However, the book ...
8
votes
4answers
531 views
Divisibility by 3?
How do you prove that a number is divisible by 3 iff the sum of its digits is divisible by 3? Please avoid using the modulus or any other operations or advanced terminology from number theory because ...
3
votes
0answers
47 views
Does a quasiperfect number exist? (n = sum of its divisors $\ne$ n,1)
Just like proper subsets of a set A are considered all subsets of A excluded A itself and $\emptyset$, some authors define proper divisors of an integer n all divisors but 1 and n itself: MathWorld, ...
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 ...
1
vote
1answer
95 views
Interesting question about irrational numbers
Find all solutions in un-ordered integers $(a,b)$ to $7-a-b=2\sqrt{10}-2\sqrt{ab}$. It would appear that the only solution to this is $a=2, b=5$. But how to prove this rigorously? Do irrational ...
0
votes
3answers
92 views
which texts on number theory do you recommend? [duplicate]
my close friend intend to study number theory
and he asked me if i know a good text on it , so i thought that you guys can help me to help him !
he look for a text for the beginners and for a first ...
2
votes
5answers
95 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$$ ...
27
votes
6answers
556 views
Is $\sqrt[3]{p+q\sqrt{3}}+\sqrt[3]{p-q\sqrt{3}}=n$, $(p,q,n)\in\mathbb{N} ^3$ solvable?
In this recent answer to this question by Eesu, Vladimir
Reshetnikov proved that
$$
\begin{equation}
\left( 26+15\sqrt{3}\right) ^{1/3}+\left( 26-15\sqrt{3}\right) ^{1/3}=4.\tag{1}
\end{equation}
$$
...
0
votes
0answers
51 views
Consecutive Integers in a Set
If we define the set $S=\{a|1\leq a \leq (41\times 61\times 101), a^{41\times 61\times 101 -1}\equiv 1( \mod (41\times 61\times 101)\}$.
I have a question which asks me to show that this set ...
1
vote
0answers
69 views
Perfect power that has digits of $0$ and $6$ only in decimal notation. [closed]
Is there a positive integer that is a perfect power and has digits of $0$ and $6$ only in decimal notation?
3
votes
2answers
66 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 ...
2
votes
2answers
125 views
Approximation to any real number by rationals
Given a real number $x$, one can show that there exists infinitely many $p,q$, such that $\gcd(p,q)=1$, and $|x-\frac{p}{q}|\leq \frac{1}{q^2}$. (There is a hint saying that I should use the pigeon ...
1
vote
1answer
32 views
An intutive explanation of natural density (asymptotic density)
I was wondering if someone can provide an intuitive explanation to natural density. I understand the concept very basically (pretty much the definition) but I can't seem to understand what natural ...
4
votes
1answer
57 views
Arithmetic progression in a subset of $\mathbb N$
What non-trivial sufficient and/or necessary conditions are there for existence an arithmetic progression (finite or infinite length) in an infinite subset of $\mathbb N$.
1
vote
1answer
75 views
How find this sum of $\sum_{d\mid n}\dfrac{G(d)}{d}$
Find
$$\sum_{d\mid n}\dfrac{G(d)}{d}$$
where $G(d)$ define the $d$ largest odd divisor, for example
$G(1)=1,\, G(2)=1,\, G(3)=3,\, G(4)=1,\, G(5)=5,\, G(6)=3$,
$G(7)=7,G(8)=1,G(9)=9,G(10)=5$
and ...
1
vote
3answers
50 views
How to find $\gcd(a^{2^m}+1,a^{2^n}+1)$ when $m \neq n$?
How to prove the following equality?
For $m\neq n$,
$\gcd(a^{2^m}+1,a^{2^n}+1) = 1 $ if $a$ is an even number
$\gcd(a^{2^m}+1,a^{2^n}+1) = 2 $ if $a$ is an odd number
Thanks in advance.
0
votes
3answers
65 views
If $x = a + b$, and only $x$ is known, how to solve what is $a-b$?
If $x$ equals to $a+b$, how can I solve what is $a-b$, knowing only $x$? (approximation will do as well, if it cannot be solved exactly)
1
vote
1answer
49 views
Showing $f(x)\equiv 0 \ (\text{mod} \ p)$ has a solution in $\mathbb{Z}$
Let $f(x) = (x^{2}-2) \cdot (x^{2}-3) \cdot (x^{2}-6)$. For every prime number $p$ how can I show that $f(x) \equiv 0 \ (\text{mod} \ p)$ has a solution in $\mathbb{Z}$.
1
vote
1answer
64 views
Prove that for any $n \in \mathbb{N}, 2^{n+2} 3^{n}+5n-4$ is divisible by $25$?
I have question
Q
Prove that for any $n \in \mathbb{N}, 2^{n+2} 3^{n}+5n-4$ is divisible by $25$?
by using induction
Thanks
3
votes
6answers
46 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 ...
29
votes
7answers
3k views
Why is every answer of $5^k - 2^k$ divisible by 3?
We have the formula $$5^k - 2^k$$
I have noticed that every answer you get from this formula is divisible by 3. At least, I think so. Why is this? Does it have to do with $5-2=3$?
2
votes
0answers
43 views
Element of a certain order in multiplicative group of residues
Let's say that $G$ is the multiplicative group of residues mod $p$, where $p$ is prime. I know that the order of an element $g \in G$ is the least $k$ for which $g^k \equiv 1 \mod{p}$.
How can we go ...
1
vote
3answers
64 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
47 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
2answers
70 views
Strategies to solve congruence problems
Which strategy is best to use when solving problems of the following sort? $$x^{29} \equiv 3\pmod {184}$$
2
votes
4answers
153 views
Are these equations true in number theory?
Are the following equations true while working in$\pmod 4$? Thank you for giving me a help.
$$3^k\equiv1,\ \text{k is even},\qquad3^k\equiv3,\ \text{k is odd}.$$
9
votes
4answers
105 views
Prove That $x=y=z$
If $x, y,z \in \mathbb{R}$,
and if
$$ \left ( \frac{x}{y} \right )^2+\left ( \frac{y}{z} \right )^2+\left ( \frac{z}{x} \right )^2=\left ( \frac{x}{y} \right )+\left ( \frac{y}{z} \right )+\left ( ...
12
votes
6answers
262 views
Is Pigeonhole Principle the negation of Dedekind-infinite?
From Wiki, "The Pigeonhole Principle":
In mathematics, the pigeonhole principle states that if n items are
put into m pigeonholes with n > m, then at least one pigeonhole must
contain more ...
6
votes
5answers
149 views
$n!>n^m$ for $n\ge?$
I want to find a natural number $N$ in terms of $m(\in\mathbb N)$, such that
$$n!>n^m \;, \forall n \ge N$$
Also, (how) can we prove that $n!-n^m$ is an increasing sequence for $n\ge N$?
I was ...
1
vote
1answer
70 views
When is “mod $n$” a congruence relation on the lattice $(\Bbb N,\gcd,\text{lcm})$?
For which $n\in \Bbb N$,
$$a\equiv b,a'\equiv b'\quad \text{implies} \quad \gcd(a,a')\equiv \gcd(b,b'),
\text{lcm}(a,a')\equiv \text{lcm}(b,b')$$
all mod $n$.
For $n=2$ it is true.
6
votes
2answers
114 views
What is the distribution of leading digits of the squares?
Inspired by How can 0.149162536... be normal?, I ask for the distribution of the leading coefficients of $1,4,9,16,25,36\ldots$. (namely $1,4,9,1,2,3\ldots$) Does a Benford-like law apply?
The online ...
2
votes
2answers
36 views
Diophantine equation $(E): 49x-6y=1$
We suppose the Diophantine equation on $\mathbb{Z}*\mathbb{Z} \quad$ $(E): 49x-6y=1$ and it's general solution is: $\{(6k+1),(49k+8): k\in \mathbb{Z} \}$.
We set $N = 1+7+7^2+...+7^{2007}$.
How can ...
4
votes
1answer
46 views
On Selmer's curve
I am trying to prove that the equation $3x^3+4y^3+5z^3 \equiv 0 \pmod{p}$ has non-trivial solutions for all primes $p$. I divide it into 3 cases: $p \equiv 0,1,2 \pmod{3}$. The cases $p \equiv 0,2 ...
1
vote
3answers
50 views
Conjecture on relationship between sum of primes and powers of 2
Let $x$ and $y$ be any odd $\mathbb{N}\geq 2$, and
$n = 2^a$ where $a$ is any $\mathbb{N} \geq 1$:
$$
{x+y \over n} = n^2, n < x < y
$$
when true, then $x$ and $y \in \mathbb{P}$ .
Anyone ...
