Tagged Questions

Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

1
vote
0answers
4 views

How to show this Legendre Symbol Problem

Let $n \in \mathbb{N}$ and $p$ an odd prime number such as $p \nmid n$, Prove that: $\exists x, y \in \mathbb{Z};\,\, \gcd(x,y) = 1$ such as $x^{2} +ny^{2} \equiv 0\, (\mod p) \iff ...
-1
votes
0answers
28 views

Too much equality?!

It seems that the concept of equality is somewhat tricky, so I was hoping someone out there can chime in on how to disentangle the below issue: Definitions of Equality If two numbers $X$ and $Y$ ...
1
vote
1answer
20 views

If $n = 2^k - 1$ for $k \in \mathbb{N}$, then every entry in row $n$ of pascal's triangle is odd.

Prove: If $n = 2^k - 1$ for $k \in \mathbb{N}$, then every entry in row $n$ of pascal's triangle is odd. I know that the $n$th row in pascal's triangle correspond to the coefficients of $(x+y)^n$: ...
0
votes
2answers
29 views

$4^x \equiv 1 \pmod{105 }$. Find the smallest integer $x$ and verify that $x$ divides 105

Through trial and error I found that the smallest integer for $x$ is 6 $4^6 = 4096 \equiv 1 \pmod{105}$. I'm just not sure if there's a better way to work out the answer. Also, it may be an error ...
0
votes
1answer
15 views

Numbers in same row of Pascal triangle not coprime

It occurs to me that any two numbers $(>1$) in the same row of the Pascal triangle seem to never be coprime. This is obviously true for the row $\binom{p}{i}$, where $p$ is prime, because every ...
5
votes
1answer
60 views

Prime number conjecture

It was suggested that I put my full conjecture up instead of specific examples. Here it is: Given any prime p>3, there exists c such that the following conditions hold: 1a. The quadratic equation ...
1
vote
2answers
18 views

Find the least $n$ such that the fraction is reducible

So I have this type of question I've never seen before. It smells like Number Theory to me, and I've never studied Number Theory, but I know a very few, very basic Number Theory facts. For instance ...
4
votes
1answer
48 views

$\sqrt{x^2+y^3}$ and $\sqrt{x^3+y^2}$ are rational

Are there infinitely many pairs of different positive rational numbers $x,y$ such that $\sqrt{x^2+y^3}$ and $\sqrt{x^3+y^2}$ are rational? Consider such a pair. Then we have $x^2+y^3=a^2$ and ...
1
vote
1answer
13 views

Cryptarithm Problem $(ABCDEF)^4 = (GHIJ)^3$

Each letter represents a distinct digit in the decimal scale. Identify the digits. $(ABCDEF)^4 = (GHIJ)^3$ I have no clue where to start.
4
votes
2answers
20 views

Bounds for lcm$(1,\dots,n)$

I need to prove there are constants $c_1,c_2 > 1$ such that $$ c_1^n < \mathrm{lcm}(1,\dots,n) < c_2^n $$ for $n$ integer, $n \geq 2$. I tried to use that $\mathrm{lcm}(1,\dots,n)=\prod_{p ...
0
votes
1answer
22 views

Prove or disprove: (i) gcd(a,q) = gcd(q,r) (ii) gcd(q,r)|b (iii) gcd(b,r) = gcd(a,q) (iv) gcd(a,r)|q

Given a,b,q,r ∈ ℤ ∋ a = bq + r. Prove or disprove the following: (i) gcd(a,q) = gcd(q,r) (ii) gcd(q,r)|b (iii) gcd(b,r) = gcd(a,q) (iv) gcd(a,r)|q Part (i) is no problem. I'm getting hung up on part ...
1
vote
0answers
18 views

The sum $\sum_{k=1}^{p-1} \frac{(p-1)!}{k} \pmod{p^2}$.

I've been trying to prove that if $p \ge 5$ is a prime, then $\sum_{k=1}^{p-1} \frac{(p-1)!}{k} \equiv 0 \pmod{p^2}$. Unfortunately, I have no good ideas on how to start a proof. I worked out the ...
2
votes
2answers
21 views

$a^2\equiv 10\pmod b$ and $a^3\equiv 33\pmod b$

Let $a,b$ be positive integers such that $a^2\equiv 10\pmod b$ and $a^3\equiv 33\pmod b$. What are all possible values of $b$? We have that $10a\equiv 33\pmod b$, but how does that determine the ...
-5
votes
1answer
37 views

Maximum negative value? [on hold]

What is the maximum negative value known in mathematics? How can I reach that maximum negative value on StackOverFlow? Thank You. Last Edit: I feel like an Electron. :p
-1
votes
2answers
38 views

Proof by induction that certain number is an integer

Prove that the number $\frac{2n^5}{5} + \frac{n^4}{2} - \frac{2n^3}{3} - \frac{7n}{30}$ is an integer $\forall n \in \mathbb{N}.$
2
votes
2answers
43 views

Find the values of k for which $\sqrt{1+\frac{k}{n}}$ is irrational.

I would like to find the positive integers $k$ for which $\sqrt{1+\frac{k}{n}}$ is irrational for all $n\in\mathbb{N}$. I was led to this question when I was making up an example for my class, and I ...
1
vote
2answers
69 views

Does $x^2 + x + 1 \equiv 0 \mod p$ have a solution?

Problem: I am trying to prove that $$ x^2 + x + 1 \equiv 0 \mod p $$ has a solution where $p$ is a prime such that $p \equiv 1 \mod 3$, without using quadratic reciprocity. I am also suspecting that ...
3
votes
1answer
26 views

Find the number of possible 4x4 matrices such that :

Find the number of possible 4x4 matrices such that : 1) each row has two 0's and two 1's 2) each column has two 0's and two 1's example : $$\large \begin{pmatrix} ...
1
vote
1answer
37 views

Suppose $x \in \mathbb{R}$. If $x^3-x>0$, then $x>-1$. Contrapositive proof

Suppose $x \in \mathbb{R}$. If $x^3-x>0$, then $x>-1$. Proof (Contrapositive). Suppose $x \leq -1$. It follows that $x^3 \leq x \leq -1$. Picking $x=-1$, the quantity $x^3-x=0$, otherwise it is ...
0
votes
1answer
22 views

Prove: If $G$ has an element of order $k$ and an element of order $m$, the order of $G$ is a multiple of lcm(k,m).

Prove: If $G$ has an element of order $k$ and an element of order $m$, the order of $G$ is a multiple of lcm(k,m). This is the same as asking to show if $k\mid n$ and $m\mid n$ then $q \mid n$. Where ...
2
votes
0answers
23 views

Proof of divisibility using factorials [duplicate]

Prove that for all $n, a \in \mathbb Z$, $n!|(a+1)(a+2)...(a+n)$. I was thinking I could do this by induction but I'm a little stuck. Here's what I have: Basis: For $n=1$, $a \in \mathbb Z$, ...
1
vote
1answer
12 views

Proof using GCDs

Given $a, b, c \in \mathbb Z$, no more than one of which is zero. Let $g_a$ denote $\gcd(a,c)$. Let $g_b$ denote $\gcd(b,c)$. Also given that $a, b$ relatively prime. Prove that $\gcd(g_a,g_b) = ...
0
votes
1answer
23 views

Proof related to RSA decryption

Can someone help me with this proof: Show that RSA decryption works for all messages a as long as the modulus m is a product of distinct primes. Thank you.
1
vote
1answer
35 views

simple question about number theory

Is there a name to the theorem that says for integers $a,b,c$ where $a$ is prime, if $a\mid bc$ and $(a,b)=1$ then $a\mid c$
1
vote
1answer
32 views

Show the congruence $x^2 \equiv a \mod p^{k+1}$ has exactly two solutions…

Show that if $p$ is an odd prime, $p \nmid a$, and the congruence $x^2 \equiv a \mod p^k$ has exactly the solutions $x \equiv \pm t \mod p^k$, then the congruence $x^2 \equiv a ...
0
votes
1answer
68 views

find the least positive residue of $1!+2!+3!+…+100!$ modulo each of the following integers

I am trying to find the least positive residue of $1!+2!+3!+...+100!$ modulo each of the following integers: a) $2$ b) $7$ c) $12$ d) $25$ and I am stuck on how to do this. I know that you have ...
1
vote
1answer
34 views

In $\mathbb{Z}_q$ where $q$ is prime, show that $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$

Question: In $\mathbb{Z}_q$ where $q$ is prime, show that $a^q=a$ for all $a\in \mathbb{Z}_q$. My attempt: To show $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$, it suffices to show that for any ...
1
vote
2answers
48 views

$\prod\limits_{i=1}^n \frac{3a_i+2}{2a_i+1}, a_i\geq 1$

$$\prod\limits_{i=1}^n \frac{3a_i+2}{2a_i+1}, a_i\geq 1$$ Claim: This product is never an integer ($a_i$ integer).
0
votes
0answers
29 views

Show $x^2 \equiv a \mod 2^{k+1}$ has either $x \equiv \pm t \mod 2^k$ or else $x \equiv \pm (2^{k-1} + >t) \mod 2^k$ as its only solutions.

We know that the congruence $x^2 \equiv 1 \mod 8$ holds for any odd $x$. Show that, if $a$ is odd and the congruence $$x^2 \equiv a \mod 2^k$$ has exactly the solutions $x \equiv \pm t \mod ...
3
votes
0answers
50 views

What is the most elementary way of proving a sequence is free of non-trivial squares?

Given the sequence A001921 $$ 0, 7, 104, 1455, 20272, 282359, 3932760, 54776287, 762935264, 10626317415, 148005508552, 2061450802319, 28712305723920, 399910829332567, \dots $$ which obeys the ...
3
votes
2answers
43 views

How to show that $n^{n!} \gt (n!)^{n}$ for $n\gt 2 \in \mathbb{N}$

Show that $n^{n!} \gt (n!)^{n}$ for $n\gt 2 \in \mathbb{N}$ I have tried induction taking the base case $n=3$ It is not going smooth however I am looking for some simpler proof, induction or ...
1
vote
3answers
24 views

Factorization probability

I'm interested in factoring large numbers. I would like to know that if I take a normal laptop and implement for example general or special number sieve and let it run all the time, what would be the ...
1
vote
1answer
30 views

Irrationality of Decimal Expansion of Primes

I've heard the proof that this number is irrational is accessible to even a novice to number theory: $\alpha = 0.2 \ 3 \ 5 \ 7 \ 11 \ 13 \ 17 \ldots$ The proof may utilize that a number is ...
0
votes
1answer
9 views

A number relatively prime to n in the integers mod n produces all the elements

Say that two integers $a,n$ are coprime. Then $r[a]_n$, where $[a]_n$ denotes the equivalence class of $a$ in the integers mod $n$, generates all the equivalence classes for the values ...
2
votes
1answer
39 views

Periodicity over the prime indices of a multiplicative sequence implies periodicity?

I have a real sequence $(a_p)$ indexed by the prime numbers which takes values -1, 0, or 1, having the property that $a_p=a_q$ whenever $p\equiv q \pmod m$, where $m$ is a fixed integer $>2$. I'm ...
0
votes
1answer
40 views

any computational analytic number theory book?

All: Can anyone recommend an introduction computational analytic number theory book ? I am mainly interested in using computer software to verify and confirm analytic number theorem, things related: ...
2
votes
1answer
12 views

How do I prove that $R=\{(x,y) \in S \times S : x\text{ divides }y\}$ is antisymmetric?

$S=\{1, 2, 3,\ldots, 1000\}$ $R=\{(x,y) \in S \times S: x \mid y\}$ My attempt: Assume $xRy$ and $yRx$. Then $x=ym$ and $y=xn$ for $m$, $n$ in Natural numbers. -So $x=xxn..$ that gets me nowhere. ...
2
votes
3answers
29 views

Solve $9x$ $\equiv 4 \mod1453$

In Underwood Dudley's Number theory book second edition chapter 5 problem 7 I encountered this problem: Solve $9x\equiv 4 \mod1453$ I know that since $gcd(9,1453)=1$, there exists a unique solution. ...
1
vote
1answer
67 views

who, by doing what, can make major contributions (breakthrough/discoveries) in math research?

I am a Math Ph.D student, had already published two small articles. I want to ask more experienced mathematician a question. What kind of person, by doing what, can make major contributions ...
3
votes
1answer
27 views

GCD of adjacent pairs take on all possible values

Given a fixed positive integer $n$. Consider the numbers $1,2,\ldots,2n$. The GCD of any pair is one of $1,2,\ldots,n$. Suppose that all $2n$ numbers are placed around a circle. Is it possible that ...
0
votes
1answer
26 views

General Behavior of Euler Totient Function

If we have two integer M and N such that $$GCD(M,N) = k$$ Then what is $$\phi(MN)$$ There is a famous identity which states: $$GCD(M,N)= 1 \rightarrow \phi (MN) = \phi(M)\phi(N)$$ And now I am ...
1
vote
1answer
25 views

Where did the sum-of-divisors function come from?

Doing a research project on a few number-theoretic functions, and I was curious, where does the sum-of-divisors function come from? Surely someone thought it up and made it a possibility. I'm talking ...
1
vote
1answer
20 views

Easy (?) estimation about prime powers

Let $N_k$ be some integers with $\sum_{k\mid n}kN_k=p^n$. How can I prove $$\frac{p^n}{n}-\frac{2p^{n/2}}{n}\leq N_n?$$
1
vote
1answer
30 views

Summation of multiplicative function $f$ where $f(p) = 1$ for $p$ prime

I have a multiplicative function $f$ with a special "base" case: For every prime $p$, $f(p) = 1$. E.g. splitting up $f(3^5 \times7^2 \times 13 \times 17)$ yields $f(3^5) f(7^2)$ which is left to be ...
1
vote
1answer
39 views

Proving that $a$ is an element of a set $A$

I am supposed to prove that if $a \in \mathbb{Z}$ and $a^2\mid a$, then $a \in \{-1,0,1\}$. If I let $B = \{-1,0,1\}$ and $\overline{B} = \mathbb{Z} \setminus B$, is it sufficient to show that $a ...
1
vote
2answers
133 views

Simple quadratic, crazy question part 2

In my previous question, I asked for advice on a general method to solve a specific problem. Many good ideas came from this, but the problem I gave was too simple and these approaches were sufficient ...
0
votes
2answers
40 views

Calculate the power series

I want to find the power series of $\frac{1}{3!}$ in the field $\mathbb{Q}_3$. In order to do this, do I have to solve the congruence $3!x \equiv 1 \pmod{3^n} \Rightarrow 6x \equiv 1 \pmod 3$? If ...
0
votes
2answers
188 views

Can anyone explain how to do this number?

Let $x,y,z \in \mathbb R$ be real numbers such that $x, y, z, x+y, y+z, z+x$ are all non-zero, and such that $\frac{xy}{x+y} , \frac{yz}{y +z} , \frac{zx}{z +x}$ are integers (i.e. belong to $\mathbb ...
2
votes
1answer
44 views

Is my understanding right on the divisiblity rule?

For a given number and a divisor. If the prime factors of the divisor can divide a number,then can I say that the divisor will divide a number. For example - 786 divide by 21 If I break 21 in the ...
6
votes
1answer
72 views

Solve $3x^2-y^2=2$ for Integers

If $x$ and $y$ are integers, then solve (using elementary methods) $$3x^2-y^2=2$$ I tried the following If $y$ is even, then $4|y^2$ and hence $2|y^2+2$ (and $4$ doesn't divide it), but ...