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

learn more… | top users | synonyms (1)

3
votes
2answers
85 views

Multiplicative order and primitive roots

Let $p$ be an odd prime and r an integer coprime to $p$. I am trying to show that if $r^{p-1}/q$ is not equal to $1$ for all primes $q$ dividing $p$, then $r$ is a primitive root modulo $p$. The hard ...
1
vote
1answer
30 views

Correct Demonstration? [duplicate]

If $$\frac{a}{(a,b)}\mid c \;\ \Rightarrow \;\ a\mid b\cdot c$$ $$\frac{a}{(a,b)}\mid c\Rightarrow c=\frac{a}{(a,b)}\cdot k\Rightarrow b\cdot c=\frac{a \cdot b}{(a,b)}\cdot k\Rightarrow b\cdot ...
1
vote
2answers
202 views

How to solve $1+2^{a}+2^{2a+1}=b^2$

I want to find all integer solutions for $1+2^{a}+2^{2a+1}=b^2$. How could I do this?
8
votes
2answers
184 views

Extending the primes

I had an idea and I'd like to find out whether it has a name or has been studied before. Imagine the natural numbers and the operations of addition and multiplication, but with the following ...
8
votes
2answers
246 views

divisibility of factorials: $a!b!(a+b)! \mid (2a)!(2b)!$

Suppose $a,b \in \mathbb{N}$, prove that $a!b!(a+b)! \mid (2a)!(2b)!.$ The only proof I know is to uses the legendre theorem I wanna know if there is a one line proof like the above hyperlink or ...
2
votes
2answers
122 views

Is Fibonacci sequence the minimum of unique pairwise sum sequence?

Let $(a_n)_{n=1}^\infty$ be a strictly increasing (condition added per earlier answer of Amitesh Datta) sequence of natural numbers where all pairwise element sums are unique. Can anyone prove or ...
4
votes
0answers
207 views

A question about odd perfect numbers

Edit [in response to a comment from anon]: Hereinafter, $N$ is a positive integer, $\sigma(N)$ is the sum-of-divisors of $N$, $\omega(N)$ is the number of distinct prime factors of $N$, and ...
0
votes
2answers
72 views

Explain why it is true that if $7^{30}$, $7^{20}$ and $7^{12}$ are not congruent to 1 mod 61, then 7 is a primitive root mod 61

Notice that $60 = 2^2 \cdot 3 \cdot 5$. Explain why it is true that if $7^{30}$, $7^{20}$ and $7^{12}$ are not congruent to $1 \mod 61$, then $7$ is a primitive root $\mod 61$. Here is what I ...
3
votes
3answers
147 views

Smallest $n$ with given number of solutions of $\frac{1}{u} + \frac{1}{v} = \frac{1}{n}$

With $n,u,v$ being positive integers, let $T(n)$ be the number of ordered pair of positive integers $(u,v)$ such that $$ \frac{1}{u} + \frac{1}{v} = \frac{1}{n}$$ What is the smallest $N$ such that ...
1
vote
5answers
279 views

$24\mid n(n^{2}-1)(3n+2)$ for all $n$ natural problems in the statement.

"Prove that for every $ n $ natural, $24\mid n(n^2-1)(3n+2)$" Resolution: $$24\mid n(n^2-1)(3n+2)$$if$$3\cdot8\mid n(n^2-1)(3n+2)$$since$$n(n^2-1)(3n+2)=(n-1)n(n+1)(3n+2)\Rightarrow3\mid ...
14
votes
2answers
4k views

Why is there no explicit formula for the factorial?

I am somewhat new to summations and products, but I know that the sum of the first positive n integers is given by: $$\sum_{k=1}^n k = \frac{n(n+1)}{2} = \frac{n^2+n}{2}$$ However, I know that no ...
0
votes
1answer
123 views

Prove : A finite subset of $\Bbb N$ has one maximum

Prove : A finite non-empty subset $S\subseteq \Bbb N$ has one maximum Compare with that: a finite subset of $\Bbb N$ has one least number.
7
votes
2answers
169 views

Is it true that if $p\neq5$ is a prime number then $1^p+2^{p-1}+\cdots+(p-1)^2+p^1\not\equiv0\pmod p$?

Is it true that if $p\neq5$ is a prime number then $1^p+2^{p-1}+\cdots+(p-1)^2+p^1\not\equiv0\pmod p$? If $p=5$ then $1^5+2^4+3^3+4^2+5^1\equiv0\pmod 5,$ but there is no such prime $p\leq40000$ ...
3
votes
3answers
272 views

Unit (last digit) of the number $7^{7^{7}}$

In a conversation on facebook, my theory professor said there know how to drive (last digit) of the number $$7^{7^{7}}$$What would be the method? For I have the slightest idea .. Oh, I still have no ...
1
vote
1answer
154 views

$n$-Bit Strings Not Containing $010$

So, I am asked to consider the number of $n$-bit strings that don't contain $010$ by considering the following $m$-leading-zero cases for $m\geq 0$, where $m\in \mathbb{N}$: $1\cdots$ $01\cdots$ ...
0
votes
1answer
51 views

Computation of determinant of a lattice

Define the following lattice in $\mathbb{Z}^2,$ $$G:=\{\mathbf{x} \in \mathbb{Z}^2:\exists \lambda \in \mathbb{Z} \ \text{such that} \ \mathbb{x}\equiv \lambda (1,1) \mod 5\}. $$ What is the ...
4
votes
4answers
393 views

How many zeroes at the end of $3^34^45^56^6 - 3^64^55^46^3$?

The quantity $3^34^45^56^6 - 3^64^55^46^3$ will end in how many zeros? This is a GRE Practice question and I have to do it without using a calculator. Can anyone help me on this?
1
vote
3answers
339 views

multiplicative Euler's $\phi$ function

Here is the pdf and array I am not understanding the proof that $\phi$ is multiplicative function i.e for relatively prime $m,n$ we have $\phi(mn)=\phi(m)\phi(n)$ There were Three Lemmas before the ...
0
votes
1answer
108 views

On primes which have 5 as a quadratic residue

Well, for which primes $p$ is $5$ a quadratic residue? I went about it this way: Let $p' = \frac{p-1}{2}$. Now, from Gauss' Lemma for Quadratic Congruences, $\displaystyle\left(\frac{5}{p}\right) ...
1
vote
1answer
74 views

Quadratic Diophantine Equation in Four Variables

Consider the equation: $$d^2 = 6 + a^2 - 3b^2 + 3c^2$$ where $a, b, c, d$ are integers. Is it necessarily the case that $a$ and $b$ have the same parity and that $c$ and $d$ have the opposite parity ...
0
votes
1answer
145 views

Paths Within a Lattice

So, I'm reading this proof: Lemma 4.2. The Schröder numbers $(r(n):n\geq0))$ satisfy $$r(n)=r(n-1)+\sum_{k=0}^{n-1}r(k)r(n-1-k)\text{ for }n\geq1,\text{ with } r(0)=1$$ Proof. The Schröder number ...
4
votes
1answer
115 views

$a \geq 2$ and $a^n+1$ is a prime number

Problem: Prove that if $a \geq 2$ and $a^n+1$ is a prime number, then $a=2$ and $n=2^k$ for some non-negative integer k. First of all, I do not understand what the question is asking me. Should I ...
4
votes
2answers
919 views

How many combinations of $3$ natural numbers are there that add up to $30$?

How many combinations of $3$ natural numbers are there that add up to $30$? The answer is $75$ but I need the approach. Although I know that we can use $_{(n-1)}C_{(r-1)}$ i.e. $_{29}C_2 = 406$ but ...
10
votes
1answer
342 views

How many zeroes are there at the end of the sum $1^1 + 2^2 + 3^3 + \cdots+ 100^{100}$?

Find the number of zeroes at the end of the sum $$1^1 + 2^2 + 3^3 + \cdots+ 100^{100}$$ I tried a lot and my answer came 4700 but it was not correct.
2
votes
1answer
57 views

Counting an orbit length in $\mathbb{Z}/q^{\alpha}\mathbb{Z}$

After working a lot of examples, I came up with the following conjecture: "Let $p, q$ be unequal primes, and $\alpha \geq 0, a$ integers. Suppose $l > 1$ is the multiplicative order of $p$ modulo ...
2
votes
1answer
651 views

Formula for pentagonal numbers

The $n$th pentagonal number $p_n$ is defined algebraically as $p_n = \frac{n(3n - 1)}{2}$ for $n \geq 1$. It can also be defined visually as the number of dots that can be arranged evenly in a ...
7
votes
1answer
98 views

Is it true that $p^{12}+5039\cdot5041$ always has a prime factor greater than $7$?

We can prove that if $p>7$ is a prime then $2^4\cdot3^2\cdot5\cdot7\mid p^{12}+5039\cdot5041.$ Is it true that $p^{12}+5039\cdot5041$ always has a prime factor greater than $7$? I have checked it ...
2
votes
1answer
337 views

divisbility of factorial and legendre theorem

I want to show that for $n \in \mathbb{N}$: $$n!(n-1)!\mid(2n-2)!$$ I think the proof uses Legendre's Theorem: Theorem: Let $f(p,n!)$ denote the highest power of $p$ dividing $n!$, then $$f(p,n!)= ...
0
votes
2answers
44 views

Arithmetic Base Conversion

Consider a number Q in a made up base system: The base system is as follows: It encodes a number as a sum of odd numbers: 1 3 5 7 9 ... If the number can be expressed as a sum of unique odds. For ...
2
votes
2answers
473 views

“Simple way” of finding number of integer solutions to $y^3=129-x^2$?

A problem appeared in an ICAS math competition paper G (for approximately 15 years olds) in 2010. The problem was: 37.A student uses trial and error to find all solutions to the question ...
2
votes
3answers
60 views

$\sqrt{d}\in{\mathbb Z}_+$ or $\sqrt{d}\in {\mathbb R}\setminus{\mathbb Q}$ for every positive integer $d$?

I just guess that the following statement is true: $\sqrt{d}\in{\mathbb Z}_+$ or $\sqrt{d}\in {\mathbb R}\setminus{\mathbb Q}$ for positive integer $d$? But I don't see a way to deal with it. I ...
1
vote
1answer
97 views

Pair Permutation of the set of Natural Numbers

Given the set of natural numbers $N$ is it possible to preform a series of operations that would result in a set with all of the different permutations of pairs? Something like: ...
1
vote
2answers
117 views

Mill's Constant Unpublished Extras

The brown paper used in the making of Numberphile's video on Mill's Constant was recently sold on eBay. Here is an image of it, from the eBay listing, The bottom two lines appear on the brown ...
4
votes
1answer
84 views

Is this proof of mine regarding prime numbers correct?

I'm required to prove the following in the textbook: Prove that if $p_1, p_2, \ldots p_n$ are distinct prime numbers with $p_1 = 2$ and $n > 1$, then $p_1 \cdot p_2 \ldots p_n +1$ can be ...
5
votes
3answers
190 views

Prove $\forall n > 2, \ \exists p\in \Bbb{P} : n < p < n!$

I need to prove that: $$(1) \ \forall n\in\Bbb{N}_{\ge2}, \ \exists p\in \Bbb{P} : n < p < n!$$ I already know how to prove the $n < p$ part; it directly follows from the proof that ...
0
votes
0answers
49 views

Harmonic Series is not an integer [duplicate]

I need to show that $H_n=1+{1\over 2}+{1\over 3}+\dots+{1\over n}$ is not an integer for $n>1$. Here I tried $n!H_n=n!+(1.3.5.\dots n)+(1.2.4.\dots n)+\dots+ (12.3.4.\dots (n-1)$ is an integer, ...
1
vote
2answers
242 views

“Interesting” Sequences

Well, here's a question i myself made up and i thought it's interesting if i share it with everyone. We call a sequence of natural numbers (for example $a$) Interesting if (all three must be true): ...
1
vote
1answer
128 views

Is $\tan (\pi x)$ never rational for all rational $x$ in the interval $(-0.5,0.5)$, with the exceptions occuring at $x=0, -0.25, 0.25$?

What I'm claiming is that I have devised a proof of this statement which says that it is true. The proof is a little long and involves trigonometry and basics of number theory, so I feel lazy to ...
4
votes
1answer
2k views

How to find in which number base the operation was done by looking at the corresponding operation in decimal system?

$$23 + 25 = 51 $$ What base is used in the above addition operation ? I have 2 methods to do this Method 1 : Through equations assume base be a $$23_a + 25_a = 51_a $$ $$2a + 3 + 2a + 5 = 5a +1 ...
2
votes
1answer
67 views

A sequence with near constant auto-correlation?

Suppose $$ x[n]= \begin{cases} x_n &, n \in P\\ 0 &, n \notin P \end{cases} $$ where $P \subset \{0,1, \cdots,N-1 \}$ and $|P|=K$ and $x_n \geq 0$. for this sequence these equations hold: $$ ...
1
vote
1answer
94 views

divisibility problem of unknown positive integer

If $a,b \in \mathbb{Z}^+$ such that $b^2+ab+1|a^2+ab+1$, prove that $a=b$. I don't have any clue on solving this problem, can anyone give me some hints? I know $a \geq b$ and $b^2+ab+1|a^2-b^2$. ...
3
votes
3answers
88 views

for every integer $n \ge 1$ one has the equality

Could any one help me? For every integer $n \ge 1$ one has the equality: $$ 1-{1\over 2}+ {1\over 3}-{1\over 4}+\dots+{1\over 2n-1}-{1\over 2n}={1\over n+1}+{1\over n+2}+\dots +{1\over 2n}.$$ ...
1
vote
1answer
47 views

we need to show gcd is $1$

I need to show if $(a,b)=1,n$ is an odd positive integer then $\displaystyle \left(a+b,{a^n+b^n\over a+b}\right)\mid n.$ let $\displaystyle \left(a+b,{a^n+b^n\over a+b}\right)=d$ $\displaystyle ...
1
vote
3answers
72 views

show numbers (mod $p$) are distict and nonzero

Let's start with the nonzero numbers, mod $p$, $1$, $2$, $\cdots$, $(p-1)$, and multiply them all by a nonzero $a$ (mod $p$). Notice that if we multiply again by the inverse of $a$ (mod $p$) we get ...
4
votes
1answer
1k views

Help understanding the proof of Lame's Theorem.

I think Lamé's Theorem is beautiful and really want to understand the proof. I am new to proofs, but after reading over the proof of Lamé's Theorem (and failing to understand it), I feel that I am ...
32
votes
9answers
9k views

Prove that $\sqrt 2 + \sqrt 3$ is irrational

I have proved in earlier exercises of this book that $\sqrt 2$ and $\sqrt 3$ are irrational. Then, the sum of two irrational numbers is an irrational number. Thus, $\sqrt 2 + \sqrt 3$ is irrational. ...
17
votes
2answers
458 views

not both $2^n-1,2^n+1$ can be prime.

I am trying to prove that not both integers $2^n-1,2^n+1$ can be prime for $n \not=2$. But I am not sure if my proof is correct or not: Suppose both $2^n-1,2^n+1$ are prime, then ...
2
votes
2answers
380 views

Arithmetic mean of positive integers less than an integer $N$ and co-prime with $N$.

Let $N>1$ be a positive integer. What will be the Arithmetic mean of positive integers less than $N$ and co-prime with $N$? Getting no idea how to proceed!
1
vote
4answers
582 views

$n$ and $n^5$ have the same units digit?

Studying GCD, I got a question that begs to show that $n$ and $n^5$ has the same units digit ... What would be an idea to be able to initiate such a statement? testing $0$ and $0^5=0$ $1$ and $1^5=1$ ...
3
votes
2answers
113 views

How many squares are there modulo a Mersenne prime?

Mersenne primes are primes of the form $M_n = 2^n - 1$. I'm wondering how many distinct natural numbers result from squaring the naturals modulo $M_n$. As an example, $M_3 = 7$. If we take the ...