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

learn more… | top users | synonyms (1)

8
votes
4answers
353 views

Decimals of the square root of $n$.

Let $a_1, \ldots, a_k$ be any sequence of digits (i.e., each $a_i$ is between 0 and 9). Prove that there exists an integer $n$ such that $\sqrt{n}$ has its first $k$ decimals after the decimal point ...
1
vote
3answers
49 views

$17x+11y \equiv 7 \pmod {29}$ and $13x+10y \equiv 8 \pmod {29}$. What are x and y?

Congruency question: if $17x+11y \equiv 7 \pmod {29}$ and $13x+10y \equiv 8 \pmod {29}$, we need to find $x$ and $y$. There may be more than one answer. Not sure how to go about this; any help ...
0
votes
1answer
31 views

If $\gcd(a,b)=D$, then why must there exists integers $x$ and $y$ such that $ax+by=D$? [on hold]

If the greatest common divisor of two integers $a,b$ is $D$, then why must there exists two integers $x,y$ such that $ax+by=D$?
3
votes
2answers
29 views

Let $Q = \{a:{1\le a\le p-1 \text{ and } a \text{ is a quadratic residue}}\}$. Prove that if $p\ge 5$, then $\sum_{t\in Q} t \equiv 0 \pmod{p}$.

If $Q = \{a: \mbox{$1\le a\le p-1$ and $a$ is a quadratic residue}\}$. How can i prove that if $p\ge 5$, then $\sum_{t\in Q} t \equiv 0 \pmod{p}$. Any help is appreciated
4
votes
1answer
344 views

Sums of Primitive Roots and Quadratic Residues when $p \equiv 3\pmod 4$

Define $$R_{p}=\{ r \mid r: \text{primitive root of p}, 1 \le r \le p \}$$ and also $$Q_{p}=\{ a \mid a: \text{quadratic residue of p}, 1 \le a \le p \}$$ $$Q_p^c=\{a \mid a: ...
1
vote
0answers
16 views

Is always two times an even semiprime at a distance $1$ or prime to the closest previous odd semiprime?

This is an observation regarding the semiprimes, also named 2-almost primes, biprimes, or the product of two primes. This week I do not have a computer, only a tablet (hospitalized with a lot of free ...
8
votes
3answers
1k views

Prove that 10101…10101 is NOT a prime.

So basically we have a number $10101...10101$ that contains $2016$ zeros and can be written as$ \sum _{ k=0 }^{ 2016 }{ 100^{ k } }$ . I want to prove that this number is not a prime without using ...
15
votes
3answers
464 views

Do 3 consecutive primes always form a triangle?

Suppose that $a$, $b$, and $c$ are any three consecutive primes other than the triple $2$, $3$, and $5$. Do they satisfy the triangle inequalities: $a + b > c$; $b + c > a$; $c + a > b$? ...
2
votes
0answers
18 views

Choosing three integers to satisfy an equation under a specific condition

Find three integers $(a,b,c)$ such that: $x*a + y*b + z*c = a + b$ only when $x = 1, y = 1, z = 0$ where $x, y$ and $z$ can be chosen as any non-negative integers. For example, choosing $a = 1$; $b = ...
0
votes
2answers
30 views

To find composite integers satisfying the given property.

Find all positive composite integers $n$ greater than $1$ such that for any relatively prime divisors $a$ and $b$ of $n$ with $a > 1$ and $b > 1$, the number $ab-a-b+1$ is also a divisor of $n$. ...
0
votes
0answers
40 views

Test if a number is in ${\mathbb R}$ [on hold]

Given a number $x$ $\in$ ${\mathbb R}$ is there a way to know if $x$ $\in$ ${\mathbb N}$ without comparing $x$ with a number in any known list of numbers? (ex. {0,1,2,3,...}) To be more specific: ...
4
votes
0answers
24 views

Proving the congruence of a Fibonacci Number [on hold]

Let $F_n$ denote the $n^{th}$ fibonacci number where $F_0 = 0, F_1 = 1$. Prove that for all primes $p > 5$, $$F_p \equiv 5^{\frac{p-1}{2}} \mod (p)$$
2
votes
1answer
19 views

How do you calculate the width of the Poset Lattice of Divisors?

Let $n = 10800 = 2^43^35^2$ I can find a set of eleven divisors of $n$ such that none divides another: $$\begin{array}{ccccc} & & & 2 3^3 & 3^35\\ & & 2^23^2 & ...
2
votes
3answers
64 views

Alternative Proof that $\sqrt{p}$ is Irrational when $p$ is Prime

I have found various proofs that $\sqrt{p}$ is irrational on this site, but I didn't find one similar to the one that I am about to post, so I am wondering if it is free of logical problems. Here is ...
0
votes
1answer
34 views

Ideals of $ord$

Let $p$ be a prime number in $\mathbb{Z}$. Let $R = R_p = \{x \in \mathbb{Q}\ |\ ord_p(x)\geq0\}$, which is a subring of $\mathbb{Q}$. (a) Show that the only nonzero ideals of $R$ are the ...
1
vote
0answers
248 views

Can an odd perfect number be divisible by 101?

Preamble - This question is an offshoot from the following earlier questions here at MSE: Can an odd perfect number be divisible by 825? Can an odd perfect number be divisible by 165? Odd perfect ...
58
votes
5answers
7k views
3
votes
2answers
138 views

Perfect numbers

Define a Perfect (capital-P) number as a natural number that is equal to the sum of its Divisors excluding 1 and the number itself. (So the Divisors of 28 are 2, 4, 7, 14, summing to 27.) Is there any ...
8
votes
0answers
272 views

A question on odd perfect numbers

Let $\sigma(x)$ be the sum of the divisors of the positive integer $x$. If $\sigma(M) = 2M$, then $M$ is said to be perfect. Currently, there are $48$ known examples of even perfect numbers -- on ...
2
votes
0answers
47 views

Is the odd part of even almost perfect numbers (other than the powers of two) not almost perfect?

Let $\sigma(x)$ denote the sum of the divisors of $x$. A number $M$ is called almost perfect if $\sigma(M) = 2M - 1$. If $M$ is an even almost perfect number, then the only known examples for $M$ ...
1
vote
1answer
176 views

Are all known $k$-multiperfect numbers (for $k > 2$) *not* squarefree?

A positive integer $N$ is said to be $k$-multiperfect if $$\sigma(N) = kN$$ where $\sigma(x)$ is the sum of the divisors of $x$ and $k$ is a positive integer. (The case $k = 2$ reduces to the ...
0
votes
1answer
147 views

even perfect numbers and primes

Thank in advance to m.s.e site. I am looking for discussions/proof of the 1) If $p ($$2^r$$/2$) is an even perfect number then $p$ should be in the form of $2^r$ - 1 2) Every even perfect number ...
5
votes
2answers
109 views

Prove that if $n$ is a perfect number, $kn$ is not

Prove that if $n$ is a perfect number, $kn$ is not. If $\gcd(k,n)=1$ then this is clear. (assume $\sigma(n)=2n$ , $\sigma(nk)=2kn$ , then $k=\sigma(k)$ but $\sigma(k)>k)$. But what about ...
0
votes
1answer
60 views

Proof that an odd perfect number must be in the form $ 36k+9$ or $12k+1$

I recently read here that an odd perfect number, if one exists, would have to be in the form $ p = 36k+9$ or $p = 12k+1$. The link says it was proven In 1953 by Touchard, but I can't seem to find the ...
3
votes
2answers
242 views

Prove that if n is an even perfect number then $\sigma(\sigma(n)) < 6n$

$\sigma(n)$ refers to the sum of all divisors function. If n is an even perfect number, then $\sigma(n) = 2n$, but why is $\sigma(\sigma(n)) < 6n$?
0
votes
1answer
260 views
5
votes
1answer
504 views

Proving that a number is perfect iff the sum of the reciprocal of its divisors is $1$

I am trying to prove the following theorem: Theorem. A number is perfect iff the sum of the reciprocal of its divisors, excluding $1$, is $1$. Thus far, this is the proof that I have managed to ...
1
vote
2answers
582 views

Sum of the reciprocals of divisors of a perfect number is $2$?

How do I show that the sum of the reciprocals of divisors of a perfect number is $2$? I tried $d_i\mid n$ with $i\in\mathbb{N},\;d_i\leq n$ then ...
3
votes
1answer
49 views

Why is $x^2+1$ divisible by $10$ if $x$ has a $3$ or $7$ in the one's place?

So I have the simple polynomial $x^2+1$. If I plug in ANY number that has a $3$ or a $7$ in the ones place $x^2+1$ is divisible by $10$. Why? Is there a reason for this? So numbers like ...
3
votes
0answers
23 views

Properties of the Discrete Logarithm Problem

I am self-studying Hoffstein's An Introduction to Mathematical Cryptography, and this is problem 2.3 (p. 107-08). Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$. (a) Suppose that ...
5
votes
1answer
851 views

Super Perfect numbers

A super-perfect number is a number with $\sigma(\sigma (n))=2n$. How can I prove that every even super perfect number is from the form $n=2^k$ when $2^{k+1}-1$ is prime. I tried every way please ...
4
votes
2answers
632 views

Can powers of primes be perfect numbers?

I need to prove the following, though I'm not 100% certain I understand the definition of a perfect number. Prove that no perfect number is a power of a prime. First of all, I'm assuming that ...
2
votes
2answers
825 views

an odd perfect number cannot be a prime number or a product of two prime numbers or power of prime number. [duplicate]

how to prove : an odd perfect number cannot be a prime number or a product of two prime numbers or power of prime number.
2
votes
4answers
65 views

the product of an odd perfect number and some even perfect number is perfect

If $a$ were an odd perfect number ,does there exist an even perfect number $b$ such that $ab$ is a perfect number?
6
votes
2answers
1k views

Discussion on even and odd perfect numbers.

First of all thank you so much for answering my previous post. These are few interesting problems drawn from Prof. Gandhi lecture notes. kindly discuss: 1) If $n$ is even perfect number then $(8n ...
4
votes
3answers
2k views

A problem dealing with even perfect numbers.

Question: Show that all even perfect numbers end in 6 or 8. This is what I have. All even perfect numbers are of the form $n=2^{p-1}(2^p -1)$ where $p$ is prime and so is $(2^p -1)$. What I did was ...
3
votes
2answers
229 views

Prove that any power of a prime is not a perfect number [closed]

How do I prove: Let $p$ be a prime, and $n$ be a positive integer. Then $p^n$ is not a perfect number. One example is when $p = 2$ and $n = 3$, the question is to show $8$ is not a perfect ...
6
votes
3answers
642 views

If $n$ is an even perfect number $ n> 6$ show that the sum of its digits is $\equiv 1 (\bmod 9)$

If $n$ is an even perfect number $ n> 6$ show that the sum of its digits is $\equiv 1 \mod 9$. I know perfect numbers are of the form $(2^{p-1})(2^{p}-1)$. I have a few trials that I have done and ...
0
votes
0answers
31 views

PID and irreducibles

Let $p$ be a prime number in $\mathbb{Z}$. Let $R = R_p = \{x \in \mathbb{Q}\ |\ ord_p(x)\geq0\}$, which is a subring of $\mathbb{Q}$. (c) Show that the only nonzero ideals of $R$ are ...
0
votes
2answers
49 views

Proof Verification: If $x$ is a nonnegative real number, then $\big[\sqrt{[x]}\big] = \big[\sqrt{x}\big]$

Let $x$ be a nonnegative real number and denote $[x]$ as the greatest integer less than or equal to $x$. We will attempt to prove that $\big[\sqrt{x}\big] = \big[\sqrt{[x]}\big]$. First suppose that ...
0
votes
0answers
40 views

Hypothetical proof of Goldbach's conjecture? [on hold]

Goldbach's conjecture: Every even number greater than 4 is the sum of two prime numbers. An equivalent statement is; For all $n\geq 2$ there exists a number $e(n)$ such that $n-e(n)$ and ...
4
votes
2answers
64 views

Prime counting function; when is it true that $\pi(n) > \pi(2n) -\pi(n)$?

Let $\pi$ be the prime counting function. Under what conditions is it proven true that $\pi(n) > \pi(2n) -\pi(n)$, if at all?
3
votes
0answers
32 views

Primes and irreducibles of $\{a+b\sqrt{-2}\ |\ a,b \in \mathbb{Z}\}$

Let $R = \{a+b\sqrt{-2}\ |\ a,b \in \mathbb{Z}\}$ Rational primes $p \geq 3$ of the form $p = a^2 + 2b^2$ factorize in $R$ as a >product of two irreducibles which are not associate. Such ...
0
votes
0answers
20 views

Is there a proof that $(n-2x)! \times n^{2x-1} > n!$ (where $x$ is a function related to the prime counting function

Is it possible to prove the following? Let $\pi$ be the prime counting function and $A(n)=\pi(2n)-\pi(n)$ $(n-2A(n))! \times n^{2A(n)-1} > n!$
3
votes
1answer
35 views

Proof Verification: Show that $\Big[\frac{x+n}{m}\Big] = \bigg[\frac{[x]+n}{m}\bigg]$

Let $m,n \in \mathbb{Z}$ and let $x \in \mathbb{R}$. Let $[x]$ denote the floor function. We will attempt to prove $$\Big[\frac{x+n}{m}\Big] = \bigg[\frac{[x]+n}{m}\bigg]$$ Suppose without loss of ...
0
votes
2answers
51 views

Prove that for any integer $n$, if $b^2$ divides $n$, then $b$ divides $n$.

Prove that for any integer $n$, if $b^2$ divides $n$, then $b$ divides $n$. Trying to figure out this proof. The proof I'm looking at is written as $n$ = any integer, if $25|n \implies 5|n$. ...
2
votes
3answers
142 views

Explain the proof that the root of a prime number is an irrational number

Though the proof of this is done in a previous question, I have some doubt about a certain concept. So I ask to clarify it. In the proof we say that $\sqrt{p} = \frac{a}{b}$ (In their lowest ...
0
votes
2answers
37 views

How to check if a a relatively small number is prime (4 digits at most)?

I have an undergrad degree. Either I missed it or they didn't teach us, but how can I check (without using a computer) if a number, say 1033, is prime?
2
votes
0answers
61 views

Counting integers from $1$ to $n$ with an odd number of divisors in {1,2,3,…,k}

Question Given $n,k$ find the number of integers between $1$ and $n$ that have odd number of divisors in {1,2,3,...,k} Example If $n=10$ and $k=3$, the numbers $1(1),5(1),6(1,2,3),7(1)$ have odd ...
0
votes
4answers
197 views

If a is an arbitrary integer, then $6|a(a^2+11)$

Pprove: If a is an arbitrary integer, then $6|a(a^2+11)$ So I substituted $k+1$ in for a and for my final step I have: $6|k^3+3k^2+14k+12$ At this point what I have left isn't divisible by $6$ ...