Tagged Questions

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

learn more… | top users | synonyms

0
votes
1answer
20 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
54 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
25 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
28 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
19 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
19 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
29 views

simple question about number theory

Is there a name to the theorem that says for integers $a,b,c$ if $a\mid bc$ and $(a,b)=1$ then $a\mid c$
1
vote
1answer
27 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
52 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
31 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
45 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
24 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
46 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
41 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
29 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
36 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
37 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
11 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
28 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
63 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
25 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
35 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
125 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
183 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
71 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 ...
1
vote
2answers
42 views

How else could we solve the congruence?

How could I solve the congruence $6x \equiv 1 \pmod { 5^4}$? I wanted to use the formula $x_n=\frac{5^4+1}{6}$, but calculating this number, we see that it is not integer. How else could we solve ...
1
vote
1answer
37 views

If $a$ divides $b$, then $a$ divides $3b^3-b^2+5b$.

Prove: Suppose $a$ and $b$ are integers. If $a\mid b$, then $a\mid3b^3-b^2+5b$. I think I have an idea of how to prove this, but I'm not entirely sure. I can prove that each individual term in ...
0
votes
2answers
58 views

What is the relation between $a$ and $b$?

Let $p$ be a fixed prime number, and $a,b$ two natural numbers satisfying $a>p,b>p$. Assume the following logical equivalence: $$a\equiv0\mod p\iff b\equiv0\mod p$$ So what is the relation ...
0
votes
1answer
36 views

Proving $2X^5 -10X+5$ is irreducible.

I'm trying to prove that $f(X)=2X^5 -10X+5$ is irreducible and the book that I'm following says that this is given by Eisenstein's Criterion. The problem is that I don't know how to use Eisenstein ...
0
votes
1answer
32 views

Equivalence classes of multiples of 3

I'm having a little trouble wrapping my head around the elements of the equivalence classes using the following definition: for m, n in N, define m ~ n if m^2 - n^2 is a multiple of 3. 1) List four ...
2
votes
0answers
42 views

Whats wrong in this proof of $10$ is a solitary number?

Friendly numbers are two or more natural numbers with a common abundancy, the ratio between the sum of divisors of a number and the number itself. Two numbers with the same abundancy form a friendly ...
2
votes
1answer
30 views

How do I write out this proof?

The following works with any number greater than the number 9. How do I write the following examples out in a proof? Take the two digits in your age for example & add then add those two numbers. ...
0
votes
1answer
13 views

finding A using with restriction $1 \leq a \leq 20$ in GCD

For what $1 \leq a \leq 20$ you are finding $a$ is it true that $a^m+a^n=x^2$ for positive integers $a,m,n,x.$ I did $a^m+a^n=x^2.$ $=a^m(a^{n-m}+1)=x^2$ We know that since $(a,b)=1$ since the ...
-4
votes
2answers
105 views

How to show that $(a \sim b \iff n | a−b)$ is an equivalence relation? [on hold]

Let $n \in \mathbb{Z}$, $n > 0$ be a fixed positive integer. Define the relation $\sim$ on the set $\mathbb{Z}$ of integers by setting $$ \forall a, b \in\mathbb{Z}\ (a \sim b \iff n | a−b). $$ ...
0
votes
1answer
36 views

What else could we do, instead of solving the congruences?

I want to find the p-adic expansion of $\frac{1}{p}$ and $\frac{1}{p^r}$ in the field $\mathbb{Q}_p$. So, do I have to solve the congruences $px \equiv 1 \pmod {p^n}, p^r x \equiv 1 \pmod { p^n }, ...
6
votes
0answers
32 views

Prove or disprove $\gcd(q,r) \mid b$ if $a = bq + r$

Prove or disprove $\gcd(q,r) \mid b$ if $a, b, q, r \in \Bbb{Z}^+ \ni a = bq +r$ I'm pretty sure it's true (I can't think of a counter example), but I don't see how to prove it. Some of my ...
3
votes
2answers
75 views

$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\dots+\frac{1}{1331}=\frac{p}{q}$; is $p$ divisible by $1997$?

if $p,q\in \mathbb{N}$ and $$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\dots+\frac{1}{1331}=\frac{p}{q}$$ why is $p$ divisible by $1997$?
1
vote
2answers
64 views

Square number yes or no?

my Problem is the following. $a$ and $b$ are positive integers and are there $x$ and $y$ so that $a+b, a+2b$ and $2a+b$ are all square numbers? Every suggestion is desired. Thanks.
0
votes
1answer
42 views

Ternary representation

Let $a$ and $b$ be two distinct positive integers which only have $1$'s and $0$'s in their ternary representation. I am convinced that $\frac{a + b}{ 2}$ should have at least one $2$ in its ternary ...
1
vote
0answers
32 views

Any results for small number Goldbach conjecture research?

It seems to me that most research results on Goldbach conjecture research are for large number. (Example: results of Vinogradov, Terence Tao, Harald Helfgott, etc). My understanding is that those ...