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

learn more… | top users | synonyms (1)

2
votes
2answers
91 views

Fibonacci Numbers and Legendre symbol

How to prove congruence below ? $$F_{p-\left( \frac{5}{p}\right)} \equiv 0 \pmod p$$ Where $\displaystyle \left( \frac{}{}\right)$ is legendre symbol, and $\displaystyle p$ is a prime number.
1
vote
2answers
50 views

How can I solve this using prime factors?

I'm stuck with this problem: $2^x \cdot 3^3 \cdot 26^y = 39^z$ for $x, y, z \in \mathbb{N}$. I know that there isn't a natural solution for the equation, but I need to "prove" it using prime factors. ...
1
vote
1answer
30 views

Proof that substitution is allowed in the integers.

I'm taking an intro to proof via number theory class and I'm trying to prove that if a|b and b|c then a|c. So you write down there exist integers k and m such that ka = b and mb = c. Then you ...
2
votes
0answers
25 views

Egyptian fraction with least possible sum

Suppose that $~a~$ and $~b~$ are coprime positive integers. Then there exists representation of $~\frac{a}{b}~$ as egyptian fraction: $$~\frac{a}{b} = \frac{1}{d_1} + \cdots + \frac{1}{d_s} ~$$ There ...
1
vote
1answer
35 views

For any a either x^2=a, x^2=-a or x^2=-1 has a solution mod p.

For any $a\quad$ either $x^2=a\quad$, $x^2=-a\quad$ or $x^2=-1\quad$ has a solution modulo p. I'm not certain if it is true, but I remember seeing something like this before. How can I prove it if it ...
1
vote
1answer
15 views

Prove variant of the division algorithm

The Division Alogrithm states that $\forall a, b \in \mathbb{N}$ where $b \neq 0$, $ \exists q,r\in \mathbb{N}$ such that $a=qb+r$ with $0 \leq r \lt b$. And one of the ways to prove it is to set $$ S ...
2
votes
0answers
44 views

Prove, by giving an example , Fermat's Little Theorem

Prove, by giving an example, that, if n is not prime, a≠0(mod n) then it is not necessarily true that { [1]n,[2]n.........[n-1]n} = {[a.1]n,[a.2]n,.......[a.(n-1)]n} could you give me any hint to ...
6
votes
2answers
88 views

example, that Wilson's Theorem is not necessarily true

Show by an example, that Wilson's Theorem is not necessarily true if $p$ is not prime. (In fact, it is not hard to show that it is never true if $p$ is not prime, but I am not asking you to do that.) ...
-1
votes
2answers
66 views

Solve equation over $\mathbb{N}\setminus\{0\}$ [closed]

I wonder whether there are any solutions besides considering $c=2^{5k+1}$ for this equation: $a^5+b^5=c^{2016}$, where $a,b,c\in\mathbb{N}\setminus\{0\}$
1
vote
1answer
56 views

Compositeness test for repunits

Is this proof acceptable ? Definition Let $R_p=\frac{10^p-1}{9} $ with $p$ prime be a repunit number . Theorem If $R_p$ is prime then $7^{\frac{R_p-1}{2}} \equiv -1 \pmod {R_p}$ Proof Let $R_p$ ...
0
votes
1answer
46 views

proof that if a|b and b|c then a|c [duplicate]

Just wanted some feed back on the following proof "if $a$ divides $b$ and $b$ divides $c$ then $a$ divides $c$" I came up with this: If $a|b$ then there exist some $x$ that $a * x = b$ and if ...
1
vote
1answer
36 views

The Number of Two-digit Primes Which the Sum of their Digits is 6

Problem: Find the number of two-digit primes which the sum of their digits is six. We had this problem in a mathematic examination. The problem can be solved by testing all two-digit primes, but ...
2
votes
1answer
87 views

Quadratic Diophantine Equation $x^2 + 2y^2 = 2013$ [closed]

Find integer values of $x$ and $y$ (if any) such that $x^2 + 2y^2 = 2013$.
2
votes
1answer
21 views

Perfect numbers of the form $12m+1$ and $\sum_{d\mid n}\frac{1}{\phi(d)}$, where $\phi(m)$ is Euler's totient function

If there are no mistakes combining Exercise 9 a) (Chapter 3, page 71) and Exercise (Chapter2, page 47) of Apostol's Introduction to Analytic Number Theory we can prove easily Lemma. If $n$ is a ...
0
votes
0answers
36 views

If $p=x^2+y^2$ is a prime number, then $\left( \frac{x+y}{p} \right) = \left( \frac{2}{x+y} \right) $

Let $p=x^2+y^2$ be a prime number. How to prove that $\left( \dfrac{x+y}{p} \right) = \left( \dfrac{2}{x+y} \right) $ (where $\left(\frac ab\right)$ denotes the Jacobi symbol)?
4
votes
1answer
27 views

Several different positive integers lie strictly between two successive squares. Prove that their pairwise products are also different.

Several different positive integers lie strictly between two successive squares. Prove that their pairwise products are also different. Let the numbers be $n$ and $n+1$. So, their squares are ...
1
vote
1answer
97 views

Quasi mathematical objects [closed]

I was looking on this post http://www.songho.ca/math/euler/euler.html and I came to the comment that says "i is not a number at all. It is an ill-formed concept. There is a vast difference between a ...
7
votes
1answer
431 views

Why there isn't any solution in positive integers for $z^3 = 3(x^3 +y^3+2xyz)$?

Consider the following Diophantine equation $$z^3 = 3(x^3 +y^3+2xyz)$$ Is there any elementary proof for the non solubility in positive integers for this Diophantine equation, where $x, y$ and $z$ ...
4
votes
1answer
38 views

Finding irrational numbers in given interval

If $~\xi~$ is irrational number then it is known that the set $~\{ p \xi + q ~ | ~ p,q \in \mathbb{Z} \}~$ is dense in $~\mathbb{R}$. Thus given some reals $~a~$ and $~b~$ one can find integers $~p~$ ...
1
vote
2answers
36 views

Let $k \geq 2$ be an integer. Let $x$ and $y$ be positive integers. Show that $x^k- y^k > 2$.

Let $k \geq 2$ be an integer. Let $x$ and $y$ be positive integers. Show that $x^k- y^k > 2$. I'm a little confused by this because this is the only information given. The book I'm using doesn't ...
1
vote
2answers
53 views

Greatest $n<1000$ such that $\left \lfloor{\sqrt{n}}\right \rfloor-2 \mid n-4$ and $\left \lfloor{\sqrt{n}}\right \rfloor+2 \mid n+4$?

My first attempt was incorrect, and it is supposed to be a middle school problem. So, if $n=k^2$ Then $k-2 \mid n-4$ and $k+2 \mid n+4$, so $n-4 \mid (n-4)(n+4)$. I then assumed the answer would be ...
0
votes
0answers
24 views

Develop a characterization for multiplicatively perfect

A positive integer n is multiplicatively perfect if $$\prod_{d\mid n} d=n^2$$ Develop and prove a characterization of all multiplicatively perfect numbers. From previous what I learned, $\prod_{d\mid ...
0
votes
0answers
42 views

Prove, using the well-ordering principle, that a set with an upper bound has a largest element?

I'm given that $S$ is a nonempty set of integers. To prove that a set with a lower bound $k$ had a smallest element, I defined another set $S'$ to be a shift of $S$: $S' = \{s + 1 − k : s ∈ S\}$ ...
0
votes
0answers
11 views

On the density of solitary numbers

Let $\sigma(x)$ denote the sum of the divisors of $x$, and let $I(x) = \sigma(x)/x$ be the abundancy index of $x$. If $X$ is the unique solution of $$I(X) = \dfrac{a}{b}$$ (for a given rational ...
3
votes
1answer
20 views

Confusion for Proof of GCD Theorem?

I'm having some trouble understanding a part of a theorem that states that the gcd between two integers exists and is unique. First it state the Euclidean Algorithm for positive integers, that for ...
2
votes
2answers
23 views

Product of three primitive roots mod prime number

Let $p$ be a prime number, and let $a,b,c$ be primitive roots mod $p$ (repetitions allowed). Is it true, in general, that $a\cdot b\cdot c$ is a primitive root? I have proved that $ab$ cannot be a ...
1
vote
2answers
57 views

For any real number $x$, if $ x^3+2x+33\neq 0$, then $x+3 \neq0$

How to solve this type of sum using indirect proof. Appreciate if anyone can explain it step by step.
0
votes
2answers
61 views

Is there a number $n$ such that $2^n$ is divisible by $31$?

Every non prime number can be represented as a product of prime numbers. I don't know much about number theory, so could you please tell me if there's a number $2^n$ that is divisible by $31$?
1
vote
1answer
47 views

$\sum_{d|n} \varphi(d)=n$

I want to solve $\sum_{d|n} \varphi(d)=n$ using Group theory. Here, $\varphi(d)$ is Euler's totient function. I think I should use $\Bbb Z_n$ and fundamental theorem of cyclic group. Then I use ...
0
votes
4answers
70 views

Prove that if $n$ is divisible by a prime number $p$ then neither $n^2 +1$ nor $n^2 -1$ will be divisible by $p$.

I know this holds for $p=3$, but can it be generalized for any prime number? Can it be generalized further for any integer $p \in \Bbb N $ ?
0
votes
0answers
89 views

Find n such that $(n - 1)! - (n - 2)! + (n - 3)! - (n - 4)! + \cdots$ modulo $n$ = 2.

An alternating factorial is the absolute value of the alternating sum of the first n factorials of positive integers. To put it algebraically, $$\mathrm{af}(n) = \sum_{i = 1}^n (-1)^{n - i}i!.$$ ...
2
votes
1answer
45 views

showing that ${kp^2\choose jp^2} \equiv {k\choose j}$ modulo $p$

Given $1\le k \le p-1$ and $1\le j \le k$, show that ${kp^2\choose jp^2} \equiv {k\choose j}$ modulo $p$ where $p$ is some prime integer. Could I receive some hints? I tried writing the expressions ...
0
votes
3answers
72 views

Prove that if $m$ and $n$ are natural numbers and $n|m$, then $n \leq m$?

$n|m$ means $n$ divides $m$, i.e. $m = kn$ for some integer $k$. I was told to use the fact that $1$ is the smallest positive integer to prove this. Using $m = kn$ and the fact that I am dealing with ...
0
votes
0answers
34 views

Fermat´s two squares theorem for primes p=1 (mod 3)

I was looking at a recent problem, that $p=1$ (mod 3) implies that there are natural numbers x and y so that $p=x^2+xy+y^2$. The proof given is complicated. I was looking for a simpler proof ...
9
votes
1answer
535 views

2016 Spain Math Olympiad final stage, problem 2

Given a prime $p$. Prove that there exist $\alpha$ such that $p|\alpha(\alpha-1)+3$, if and only if there exist $\beta$ such that $p|\beta(\beta-1)+25$. My solution: Using quadratic residuu we ...
3
votes
1answer
1k views

Find the sum of Fibonacci Series

I have given a Set A i have to find the sum of Fibonacci Sum of All the Subset of A ...
0
votes
0answers
50 views

About an integer factoring algorithm

I have been toying with the following algorithm: ...
1
vote
2answers
33 views

Proof regarding the euler totient function

Let $m$ be a positive integer, prove that $$\sum_{\substack{d\mid m\\d>0}} \varphi(d) = m.$$ Recall $$\sum_{\substack{d\mid m\\d>0}} \varphi(d) = \sum_{\substack{d\mid m\\d>0}} ...
3
votes
3answers
76 views

if $(a,b,c)$ is a Pythagorean triple then $a$ or $b$ or $c$ can be divided by 3 [closed]

Prove that if $(a,b,c)$ is a Pythagorean triple then $a$ or $b$ or $c$ can be divided by 3
1
vote
3answers
44 views

Question about a specific part of proving $\sqrt 7$ is irrational

I have a question that wants me to prove that the square root of $7$ is irrational. So I know we need to use proof by contradiction, then $7 = \frac{a^2}{b^2}$ where $a$ and $b$ are coprime. Then $a^2 ...
2
votes
1answer
17 views

Even perfect numbers and a relationship with polygonal numbers

Let $\sigma(m)=\sum_{d\mid m}d$ the sum of divisors function, for example $\sigma(6)=1+2+3+6=12$. Question. I don't know if this exercise was in the literature, and I believe that I know how ...
3
votes
0answers
40 views

Bezout Coefficients produced by Extended Euclidean Algorithm for $a$ and $b$

I was trying the Extended Euclidean Algorithm on various pairs of numbers to find a logic on the Bezout Coefficients produced. But, I am confused about the nature of the coefficients. I found the GCD ...
2
votes
1answer
60 views

$\Bbb Z_m \times \Bbb Z_n$ isomorphic to $\Bbb Z_{\operatorname{lcm}(m,n)}\times \Bbb Z_{\gcd(m,n)}$

I want to show the title. Let $\Bbb Z_{\operatorname{lcm}(m,n)}=\langle x\rangle$, $\Bbb Z_{\gcd(m,n)}=\langle y\rangle$, $\Bbb Z_m=\langle z\rangle$, $\Bbb Z_n=\langle w\rangle$ and $d=\gcd(m,n)$. ...
0
votes
1answer
251 views

Bijection of positive rational numbers with the natural numbers

In what position does the number $\frac{14}{15}$ appear in the bijection of the positive rational numbers with the natural numbers? The first few terms of the bijection are: $\frac 11$, $\frac12$, ...
0
votes
3answers
58 views

Prove that $\forall \ n \in \mathbb{N}, \ n^2 + 3n + 2$ is not prime [closed]

Can anyone explain step by step how to use direct proof for solve this type of sum. Seriously I am confused with direct proof.
0
votes
2answers
270 views

What possible remainders do perfect cubes leave when divided by $7$?

Would I use the quotient remainder theorem for this? How can I figure out the remainders perfect cubes leave when divided by a certain number without just listing perfect cubes and dividing by $7$ to ...
2
votes
2answers
71 views

$\left(-1\right)^0$: What is it and why?

I tried to search for this question here but couldn't find any. But probably there is a good chance that someone already asked it. What is $\left(-1\right)^0$? I get mixed results when I try to ...
3
votes
1answer
74 views

$p = x^2 + xy + 3y^2$ if and only if $p \equiv 1$, $3$, $4$, $5$, $9$ mod $11$? [duplicate]

For a prime number $p \neq 11$, do we have $p = x^2 + xy + 3y^2$ for some $x$, $y \in \mathbb{Z}$ if and only if $p \equiv 1, 3, 4, 5, 9$ mod $11$? An example where this is true:$$5 = 1^2 + 1 \times ...
0
votes
6answers
63 views

Prove $4n < n^2 - 7$ for $n$ is greater than or equal to $6$

We are supposed to be proving this by induction and I know the basis is true $4(6) < 36-7$ and the inductive hypothesis is $4n<n^2-7$ for n $ \ge $6 but I am not sure what the next step is. Do I ...
2
votes
1answer
50 views

Find all nonnegative integer solutions to $x^3 + 8x^2 − 6x + 8 = y^3$.

Find all nonnegative integer solutions to $x^3 + 8x^2 − 6x + 8 = y^3$. The only solution I have found is $x=0$. I have tried proving it by congruences and have had no success. I don't know how ...