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

learn more… | top users | synonyms

1
vote
1answer
28 views

Condition when inequality with numbers is true

Let $n\geq 1, m>1, k\leq n$. I am trying to find condition on $m,$ that $$ 4\sqrt{\pi}(2m)^{mn}\leq2^k $$ Thank you.
1
vote
2answers
417 views

proving that a number is a perfect square

I need help with this problem: $K$ is equal to $111\ldots111 - 22\ldots22$ where $1$ is used $2n$ times and $2$ is used $n$ times. Prove that $K$ is a perfect square. It is true, but I can't find a ...
5
votes
3answers
192 views

Axiomatically define a function that can solve otherwise impossible differential equations, like $i$ solves otherwise impossible polynomial equations

We all know that roots of polinomials are not always real numbers or when we take the square root of a negative number, we need to immmediately define an imaginary number called $i$ or $j$ for futher ...
0
votes
4answers
117 views

Fractional Parts Proof

OK, here are two questions out of Nathanon's Additive Number Theory from the section on fractional parts ($\S$4.4). I think I'm missing something. I don't understand what there is to prove? Let ...
1
vote
1answer
38 views

Possible values of $N$

Find the number of values of $N$ such that the below expression is an integer: $(n+1)^2\over n+7$ is an integer
1
vote
0answers
58 views

When is the factorial of a number triangular? [duplicate]

Possible Duplicate: Triangular Factorials Extending this question, what are the solutions $(m,n)$ of this equation? $\sum_{k=1}^m{k} = n!$ I know $(1,1)$, $(3,3)$, and $(15,5)$. Are ...
2
votes
2answers
126 views

A question about rational.

Is that true : Every positive rational number $q$ can be written as $q = \sum_{i=0}^{k}1/n_i$ , where $n_i,k$ are positive intergers and $n_i\not=n_j$ if $i\not=j$.
2
votes
3answers
281 views

When is a factorial of a number equal to its triangular number?

Consider the set of all natural numbers $n$ for which the following proposition is true. $$\sum_{k=1}^{n} k = \prod_{k=1}^{n} k$$ Here's an example: $$\sum_{k=1}^{3}k = 1+2+3 = 6 = 1\cdot 2\cdot ...
2
votes
1answer
116 views

number of divisors of a composite number

Consider the power series $\sum_{n\ge1} a_n z^n$ where $a_n =$ number of divisors of $n^{50}$. then the radius of convergence of $\sum_{n\ge1} a_n z^n$ is (1) 1 (2) 50 (3) $\frac 1 {50}$ (4) 0
2
votes
3answers
96 views

In the ring of $\mathbb Z[i]$ divide $7+2i$ by $2+i$.

In the ring of $\mathbb Z[i]$ use our division algorithm divide $7+2i$ by $2+i$. $$\frac{7+2i}{2+i}\cdot \frac{2-i}{2-i}=\frac{16-3i}{5}=\frac{16}{5}-\frac{3}{5}i$$ Does this mean you cannot divide ...
1
vote
4answers
86 views

In the ring $\mathbb Z[i]$ explain why our four units $\pm1$ and $\pm i$ divide every $u\in\mathbb Z[i]$.

In the ring $\mathbb Z[i]$ explain why our four units $\pm1$ and $\pm i$ divide every $u\in\mathbb Z[i]$. This is obviously a elementary question, but Gaussian integers are relatively new to me. I ...
1
vote
2answers
27 views

Argue that none of the $q_j$ are 3 and that each $q_j$ is different from each $p_i$ for $7(p_1\cdot p_2\dotsb p_s)+3=q_1\cdot q_2 \dotsb q_t$

Let $7(p_1\cdot p_2\dotsb p_s)+3=q_1\cdot q_2 \dotsb q_t$ where the $p_1,p_2,\dots,p_s$ and $q_1,q_2,\dots,q_t$ are primes and where none of the $p_i$ is $3$. Argue that none of the $q_j$ are 3 and ...
2
votes
3answers
181 views

Primitive roots and Prime Numbers

Question: "Show that if $p$ is prime and $\gcd(d,p-1) = 1$, then every positive integer less than p is congruent modulo $p$ to the $d$-th power of some other integer." I understand that this is ...
11
votes
3answers
431 views

Leading Digit of $2^{4242}$

How could I solve this problem? Find the first digit of $2^{4242}$ without using a calculator. I know how to find the last digit with modular arithmetic, but I can't use that here.
1
vote
1answer
36 views

Let $A=\{6,10,30\},B=\{3,5\}$ and $P(x,y)=$ $x$ is divisible by $y$. Are these statements true?

Let $A=\{6,10,30\},B=\{3,5\}$ and $P(x,y)=$ $x$ is divisible by $y$ State whether it is true or false for the below statements. 1.For any odd integer $x$ in $A$, for any $y$ in $B$, $P(x,y)$ ...
0
votes
1answer
489 views

Real Analysis 1 vs Real Analysis 2?

Note: I am not sure if this is the correct place to ask these types of questions, so please let me know if I should remove my question. I'm taking Real Analysis 1 this semester, and was thinking of ...
0
votes
1answer
98 views

Poincare series

I understand the concepts used in then Poincare series, but I don't know how to compute the Poincare serie of an specific polinomyal, for example $x^2-a$, what must I do?
10
votes
2answers
705 views

Reference request: Clean proof of Fermat's last theorem for $n=3$.

I have seen a proof for FLT, $n=3$ using factorisation in the ring of Eisenstein integers, but it's quite long and convoluted; I am wondering if there is a more 'advanced' proof which avoids infinite ...
4
votes
5answers
222 views

Primes of the form $a^2+b^2$ : a technical point.

One can classify the prime integers $p$ which can be written as $p=a^2+b^2$ for some integers $a,b\in\mathbb{Z}$ by studying how $p$ decomposes in the ring of Gauss integers $\mathbb{Z}[i]$. Most ...
2
votes
2answers
344 views

Finding positive Bézout coefficients

If I have Bézout coefficients (obtained using extended Euclidean algorithm) and one of them is negative, what is the easiest way to obtain positive Bézout coefficients?
1
vote
2answers
67 views

How many squares can be congruent modulo a prime?

If we suppose that we are interested in non-negative integers less than a prime $p$, is it possible to find more than two of these integers, such that, when squared, are all congruent modulo $p$? In ...
1
vote
2answers
34 views

How many different terms in this sequence?

How many different terms in this sequence? $u_k=\left\lfloor \frac{k^2}{2013}\right\rfloor$, $k=1,2,3...2013$ Thanks so much
4
votes
2answers
178 views

Prove $\lim_{n\to\infty} \sum\limits_{k=1}^n \frac{\Lambda(k)}{k}-\ln(n)=-\gamma $

How do I prove$$\lim_{n\to\infty} \sum\limits_{k=1}^n \frac{\Lambda(k)}{k}-\ln(n)=-\gamma $$ Where $\Lambda(k)$ is the Von-Mangoldt function, and gamma is the euler gamma constant
2
votes
2answers
326 views

What prime powers differ by one

I thought this would be a hard problem but I found a link that seems to ask the answer to this question as a homework problem? Can somone help me out here, are there an infinite number of prime powers ...
1
vote
1answer
156 views

RSA solving for primes p and q knowing n = pq and p - q

I was also given these: $p+q=n-\phi(n)+1$ $p-q=\sqrt((p+q)^2-4n)$ $\phi(n)=(p-1)(q-1)$ $p>q$ I've been trying to manipulate this as a system of equations, but it's just not working out for me. I ...
5
votes
1answer
361 views

Odd perfect number divisors

I have a tough one today. Show that if $n$ is an odd perfect number, then not all of $3$, $5$, and $7$ are divisors of $n$. Any and all help is appreciated. Thanks very much.
3
votes
2answers
277 views

Ceiling function inequality

In class, we used the fact that $\lceil{a + b \rceil} \geq \lceil{a}\rceil + \lfloor{b}\rfloor$. However, we weren't given a proof of this statement. I am interested to see how this works. Can anyone ...
1
vote
1answer
66 views

For any odd integer $x,y$, $(x^2+2) \nmid (y^2+4)$ [duplicate]

Possible Duplicate: Quadratics and divisibility Prove that for any odd integers $x$ and $y$, we have $(x^2+2) \nmid (y^2+4)$
1
vote
1answer
89 views

Prove the binary quadratic forms $5x^2+xy+y^2$ and $x^2-xy+5y^2$ are equivalent

I need to show the binary quadratic forms $$5x^2+xy+y^2$$ and $$x^2-xy+5y^2$$ are equivalent. We've only touched on quadric forms, and the only definition I have for "equivalence" is that one can be ...
2
votes
2answers
395 views

Relation between $\sigma (N)$, $\tau (N)$, and $\varphi (N)$

How to prove $$\sum\limits_{d\mid n} {\sigma (d)\varphi (n/d) = n\tau (n)}$$ and $$\sum\limits_{d\mid n} {\tau (d)\varphi (n/d) = \sigma (n)}$$ where ${\sigma (N)}$ is the divisor function, ${\tau ...
6
votes
1answer
189 views

Primes of the form $x^2+5xy+5y^2$

Trying to describe all primes of the form: $$x^2+5xy+5y^2$$ A hint was given with the question to show all primes $p$ for which 5 is a quadratic residue mod $p$. I've been able to show that all ...
2
votes
1answer
39 views

Let $q$ be a prime of the form $4k+3$. If $2q+1$ is prime, then $2q+1$ divides $2^q−1$.

This is the theorem I need to show: "Let $q$ be a prime of the form $4k+3$. If $2q+1$ is prime, then $2q+1$ divides $2^q−1$." I need to show this to show that $2^{251} - 1$ is not a Mersenne Prime.
5
votes
1answer
101 views

$2^{251 }-1$ not Mersenne Prime

I need to show that $2^{251} - 1$ is not a Mersenne prime. Hard because $251$ is prime. If i can show that a prime $p$ is congruent to $3 \bmod 4$, and $q = 2p + 1$ is a prime, then $2^p$ is congruent ...
1
vote
3answers
165 views

Infinite number of primes

This is an axiomatic proof, but I don't know how to start the exercise first one, I have to proof that if $q$ divides $a^p-1$ then $q$ divides $a-1$ or $q=2pt+1, t\in \mathbb{Z}$, and, if $q$ ...
8
votes
1answer
558 views

Numbers representable as $x^2 + 2y^2$

I need to describe all numbers of the form $x^2 + 2y^2$. So far I've reduced the problem to primes, and showed p=2 satisfies it. I've also shown that any primes mod 5 or 7 can't be a written in this ...
1
vote
2answers
2k views

Determine all primes p for which 5 is a quadratic residue modulo p

I need to determine all primes $p$ for which $5$ is a quadratic residue modulo p. I think I'll need to use quadratic recprocity laws to do this, i.e., I need to need to find numbers $p$ where ...
0
votes
1answer
201 views

Existence of a limit, prime number theorem

Why does one have to prove that the limit below exists, in order to prove the prime number theorem? $$ \lim_{x \rightarrow \infty} \frac{\psi(x)}{x} $$ Doesn't the fact that the Chebyshev function is ...
2
votes
2answers
77 views

Divisibility explanation needed

I thought I proved the following two divisibility statements but later I found out I was wrong. Could someone explain them? 1) For primes $q\geq 2$, $2^q-1$ is divisible by some prime $p$ such that ...
3
votes
1answer
50 views

The uniqueness of $\mu$ totient function for this two properties

I know that the $\mu$ totient function have this two important properties: The first one is that, supposing that $f$ is a multiplicative arithmetic function, I have that $g=f\star u$ if and only if ...
2
votes
1answer
86 views

Number of solutions of $x^2 \equiv 1 \pmod{2^rq}$

I need to show that the number of solutions of $$x^2 \equiv 1 \pmod{2^rq}, (2^rq) \in \mathbb{N}$$ is $2^{s+t}$ where $s$ = #distinct prime divisors of $q$ and $t$ = 0,1,2 according as $r\le1$, ...
2
votes
1answer
100 views

Absolute Convergence of Dirichelet Series

The exact series I must show converges absolutely is: $$\sum_{n=1}^{\infty}{\frac{d(n)^r}{n^s}}$$ for $s > 1$, $r\in \mathbb{N}$ and where $d(n)=\#\text{ of divisors of } n$. I've been able to ...
0
votes
1answer
128 views

Two questions on finding trailing digits in (large) numbers and one on divisibility

Without using a calculator, how can we solve the following? How do we find the number of zeros at the end of $600!$ What are the last 3-digits of $171^{172}$? What is the sum of all positive numbers ...
2
votes
0answers
51 views

Is there a natural , $1\leq t\leq n$ such that $(n,t)=1$ and $\frac{n}{(n,t-1)}=d$?

Let $n$ an even number and $d$ be a divisor of $\frac{n}{2}$. Is there a natural number $1\leq t\leq n$ such that $(n,t)=1$ and $\frac{n}{(n,t-1)}=d$? $(n,t-1)$ is largest divisor of $n$ and ...
0
votes
2answers
55 views

Find all positive integers $a$ for which there exists some positive integer $b$ s.t. $(2^a-1)\mid(b^2+9)$

Find all positive integers $a$ for which there exists some positive integer $b$ s.t. $(2^a-1)\mid(b^2+9)$
0
votes
1answer
53 views

There exists finitely many numbers s.t.: “the number of digits = total number of its prime divisor”

Show that there exists finitely many numbers $n$ satisfying: "the number of digits" $=$ total number of its prime divisor" For instance, $18 = 3^2*2$ satisfies, while $27 = 3^3$ does not.
2
votes
1answer
80 views

Divisibility problem with primes

I got stuck with another divisibility problem. Prove that there exist infinitely many primes p that can be represented in the form $p=4k-1$, where k is a natural number, such that $2^q-1 \equiv 0 ...
1
vote
1answer
141 views

There is solution for $x^{16} \equiv 256 \pmod p$ for all prime $p$. Prove or disprove it.

The congruence equation, $x^{16} \equiv 256 \pmod p$ for all prime $p$, is solvable. Prove or disprove it. Here I am thinking of proving that $y^2 \equiv 256 \pmod p$ has solution since the quadratic ...
2
votes
3answers
2k views

Proof (Divisibility): If a|b and b|c then a|c

Ok, here is what I have for the proof of this conjecture. Let me know if I'm on the right path? all input appreciated. There exist integers $j$, $k$, and $m$, such that, $b = aj $ and $ c = ajk.$ ...
2
votes
1answer
334 views

Theorems similar to Euler's theorem ($a$, $n$ are not coprime)

It is well known that if $\gcd(a,n)=1$, then $a^{ϕ(n)}=1$ mod $n$. Are there any results similar to Euler's theorem that can be used when $a$ and $n$ are not coprime. Feel free to add any ...
3
votes
3answers
814 views

Modulo Congruence: How does $a=b\bmod n$ implies $a$ and $b$ have the same remainder when divided by $n$?

How does $a=b\bmod n$ implies $a$ and $b$ have the same remainder when divided by $n$? I don't understand the huge jump from modulo to implying the same remainder. I see that $a=b\mod n$ implies ...