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

learn more… | top users | synonyms (1)

0
votes
1answer
55 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 ...
7
votes
1answer
327 views

Convergence of $\sum_\lambda \frac{1}{1-\lambda x}$ where $p(\lambda)=0$ for a certain polynomial $p$

The powers of the roots $\lambda$ of these polynomials $$p_n(x):=\sum_{k=1}^{n-1}\frac{n!}{(n-k)!}x^{k-1}$$ (compare with the $p_n$ here) sum to these values $$\sum_\lambda ...
2
votes
1answer
49 views

Existence of two natural number satisfying a given condition in a given set

Suppose $A=\{1,2,\dots,112\}$, $B \subset A$ and the number of elements in $B$ is greater or equal to 37. Then, is it true that there always exist two elements $x,y \in B$ such that $x-y\in ...
1
vote
0answers
58 views

Looking for help understanding the proof behind Schnirelmann Theorem: $d(A+B) \ge d(A) + d(B) - d(A)d(B)$

I am trying to understand the proof by Gelfond & Linnik that: $$d(A+B) \ge d(A) + d(B) - d(A)d(B)$$ Here's what I understand: Let $A$, $B$ be infinite sequences of integers starting with $0$ ...
1
vote
2answers
259 views

Primitive Roots Proofs

I am stuck on how to prove these two questions: (1) Let r be a primitive root of the prime $p$ with $p$ congruent to $1$ modulo $4$. Show that $-r$ is also a primitive root. (2) Let n be a positive ...
5
votes
1answer
172 views

Find all solutions of the equality $y^2=x^3+23$ for integers $x,y$

Find all solutions of the equality $y^2=x^3+23$ for integers $x,y$ I guess, that x cannot be even. because we can apply mod 4 test say $x=2k$ then $y^2=8k^3+23\equiv3\mod(4)$ but, this is not ...
-1
votes
1answer
37 views

Phi-Function Congruence

Let n be a positive integer such that $n>1$. Show that for any positive a, $a^{n}\cong a^{n-\phi(n)}$ mod n. I think that this needs the fact that if positive integers x,y with $y>1$ then ...
1
vote
1answer
69 views

Complex Numbers, Complicated Powers

We know there are two non-real imaginary numbers like $a$, $b$ such that the power $a^{b}$ is a real number. For example we have $i^{i}=\frac{1}{\sqrt{e^{\pi}}}$. Question: Are there two non-real ...
0
votes
1answer
115 views

The Question About Euler-Phi Function In Elementary Number Theory.

I have a question in elementary number theory. The Problem is : Prove that there is no solution to the equation $f(n)=14$ (Now, $f$ is the Euler-Phi Function), and that $14$ is the smallest ...
2
votes
0answers
66 views

Smart way to prove this useful inequality?

I want to show the following elementary inequality: $$((|a|+|b|)^p + (|c|+|d|)^p)^{\frac{1}{p}} \le (|a|^p+|c|^p)^{\frac{1}{p}} + (|b|^p+|d|^p)^{\frac{1}{p}}$$ and we have $p \ge 1$. Does anybody ...
2
votes
0answers
53 views

Improving a diophantine approximation

Let $x\in \mathbb T^d=\mathbb R^d/\mathbb Z^d$ and $p/q\in\mathbb Q^d/\mathbb Z^d$ be such that $\|x-p/q\| \leqslant t$ (with $t$ small) and $q\leqslant Q$ can I say that for all $m\in\mathbb N^\star$ ...
6
votes
0answers
148 views

Twin Prime Powers

What are all the possible triplets of numbers $a$, $b$, $c$ such that $a+2=b$, $a+4=c$, and all $3$ are prime powers (where one must be a power of $3$)? I'm aware of the cases for when they are ...
6
votes
3answers
126 views

Prove $x + y$ is divisible by $11$. Is my solution correct? [duplicate]

If $x$ & $y$ are natural numbers, and $56 x = 65 y$, prove that $x + y$ is divisible by $11$. Solution) $56$ and $65$ are relatively prime So, $65∣x$ and $56∣y$ Let $x = 65m$ and $y = 56n$ ...
1
vote
2answers
77 views

Remainder Question

What process do I use to show what is the remainder when 14 × 7^36 + 92 when divided by 8? Is it the same to show the remainder of ...
2
votes
2answers
153 views

Criteria for irrationality of real numbers

Concerning the criteria for irrationality: Theorem says "A number $\alpha$ is irrational if and only if for every $\epsilon >0$ there exist integers $h$ and $q$ such that $0 < | q\alpha - h | ...
1
vote
2answers
153 views

ABC Conjecture: Simple example showing $\epsilon$ is necessary

I was looking over Lang's discussion of the abc conjecture in his famous Algebra tome. He says We have to give examples such that for all $C>0$ there exist natural numbers $a$,$b$, $c$ ...
2
votes
1answer
50 views

Integral value of z

Given two rationals $x,y \in \mathbb Q$. If we have $x^2 + y^2 = z$ , then what all integral values can $z$ take ?
1
vote
1answer
56 views

cost of providing school dinners

The graph of the cost of providing school dinners versus the number of children is a straight line not passing through the origin and increases as the number of pupils increases. For $200$ students ...
1
vote
1answer
44 views

Primes taking the form $a+nb$

If $a,b$ are two coprime positive integers, can we find infinitely many positive integer $n$, such that $a+nb$ is a prime?
1
vote
1answer
57 views

How many combinations are possible [closed]

$2013$ is divisible by $3$. $ \ 3012$ is also divisible by $3$. They both have consecutive digits. How many total numbers between $1\ 000 - 10 \ 000$ meet these conditions of having consecutive ...
4
votes
3answers
108 views

Is there a $3\times 3$ magic square adding up to $7$.

I suspect that there is no magic square with natural number entries (matrix where each row, column and long diagonal add up to the same number) which would add up to $7$. There is no restriction on ...
0
votes
2answers
75 views

Solve linear $\,ax + b = 0$ in $Z_N$

So I'm really struggling to tackle the above question. I don't know how to approach it at all. I'm aware that I'm trying to solve for $x$, but given $Z_n$ I'm confused. The question is related to an ...
5
votes
1answer
204 views

How to prove this inequality $\pi(x) > \log x - 1$ involving the prime counting function?

Problem Prove that $\pi(x) > \log x - 1$. Progress Based on a hint and very elementary methods, I got that $$ \prod_{p \leq x} (1-p^{-1})^{-1} \leq \prod_{k=2}^{\pi(x)+1} (1-k^{-1})^{-1}. $$ The ...
1
vote
1answer
60 views

Is there a base for each positive integer where this number can be represented a string of n (base - 1) digit?

How are called positive integer numbers that have the following property of being represented as: $$ N = \sum_{k=0}^n{(B-1)B^k} = (B - 1)\sum_{k=0}^n{B^k} $$ with $N$ a positive integer number, $B$ ...
9
votes
3answers
254 views

Show that $(n!)^{(n-1)!}$ divides $(n!)!$

Show that $(n!)^{(n-1)!}$ divides $(n!)!$ I found this question in a text he was reading about BREAKDOWN OF PRIME FACTORS IN FACT, I decided many years, have posted some here to help, but this ...
2
votes
2answers
104 views

Find all integers n which satisfies $1^n+9^n+10^n=5^n+6^n+11^n$

Find all $n\in\mathbb Z$ which satisfies $1^n+9^n+10^n=5^n+6^n+11^n$ for $n=2\ or\ n=4$ it is equal but are there other numbers?
2
votes
1answer
66 views

Relatively Prime problem

If $a$ and $b$ are relatively prime integers then $b$ and $a$ plus some multiple of $b$ are also relatively prime. I can see how it works for concrete examples but can't prove it. i.e. $(a,b)=1$ ...
2
votes
1answer
374 views

If 4n+1 and 3n+1 are both perfect sqares, then 56|n. How can I prove this?

Prove that if $n$ is a natural number and $(3n+1)$ & $(4n+1)$ are both perfect squares, then $56$ will divide $n$. Clearly we have to show that $7$ and $8$ both will divide $n$. I considered ...
3
votes
1answer
46 views

Showing that an integer is a strong pseudoprime

I need to show that $n=1,373,653$ is a strong pseudoprime to the bases 2 and 3. I've used Fermat's Little Theorem on the prime decomposition of $n=829\cdot1657$ to get $$2^{828}\equiv1\ mod\ 829\quad, ...
1
vote
1answer
41 views

on roots of an equation

Let $A=\{0,1,\cdots,d-1\}$. Consider the set $P(n)=\{(x,y)\in A\times A:x+y=n\}$. Consider the function $F(X)=\sum_{n=0}^{2(d-1)} \# P(n) X^n$, where $\#$ denotes the cardinality of $P(n)$. For the ...
1
vote
1answer
60 views

Number theory fermat's number

Why must $n$ be a power of two when $2^n + 1$ is prime and $n > 0$? I understand that $2^n+1$ is prime only if $k$ is a power of $2$, butI don't understand why. Can anyone explain this ...
0
votes
1answer
41 views

Factors of a number.

If $M$ is an even number. Then what are the possible even factors of $M$ ? I am thinking that maximum possible even factors are $\frac M2,\frac M4,\frac M8, \frac M{16}$ and so on Are there any even ...
1
vote
1answer
36 views

show that if $m,n\in\mathbb{N}$ are such that $(m,n)=1$, then $\frac{(m+n-1)!}{m!n!}\in\mathbb{N}.$

show that if $m,n\in\mathbb{N}$ are such that $(m,n)=1$, then $$\frac{(m+n-1)!}{m!n!}\in\mathbb{N}.$$ I have a theorem (shown in my text) that says $$\fbox{If $a_1,...,a_m\in\mathbb{N}^*$ then ...
5
votes
2answers
118 views

Show that there is no natural number $n$ such that $3^7$ is the largest power of $3$ dividing $n!$

Show that there is no natural number $n$ such that $7$ is the largest power $a$ of $3$ for which $3^a$ divides $n!$ After doing some research, I could not understand how to start or what to do to ...
1
vote
1answer
382 views

weight of heaviest box?

A shipping clerk has five boxes of different but unknown weights each weighing less than 100 kg. The clerk weights the boxes in pairs. The weights obtained are 110, 112, 113, 114, 115, 116, 117, 118, ...
1
vote
1answer
77 views

Additive properties of sequences: trying to understand Schnirelmann density

I have started reading Gelford & Linnik's elementary methods in analytic number theory (1965). They define a sequence $A$ of integers as: $$0, a_1, a_2,a_3,\dots$$ where $$0 < a_1 < a_2 ...
4
votes
3answers
81 views

If $N$ is a multiple of $100$, $N!$ ends with $\left(\frac{N}4-1 \right)$ zeroes.

Did certain questions about factorials, and one of them got a reply very interesting that someone told me that it is possible to show that If $N$ is a multiple of $100$, $N!$ ends with ...
2
votes
1answer
46 views

Find the smallest value of $n$ so that the greater potency of $5$ which divides $n!$ is $5^{84}$. What are the other numbers that enjoy this property?

Find the smallest value of $n$ so that the greater potency of $5$ which divides $n!$ is $5^{84}$. What are the other numbers that enjoy this property? I thought I would put together an equation ...
2
votes
1answer
2k views

Prove the proposition: there are infinitely many primes of the form 4k + 3, where k ≥ 0 is an integer

Proposition 2. there are infinitely many primes of the form 4k + 3, where k ≥ 0 is an integer. (a) Let n ∈ N. Suppose q1,q2,...,qn are positive integers such that for all 1 ≤ i ≤ n, each qi = 4ki + ...
8
votes
2answers
164 views

Find the greatest power of $104$ which divides $10000!$

Find the greatest power of $104$ which divides $10000!$ I thought $$104=2^3\cdot13$$ so I have to find $n$ such that $$(2^3\cdot13)^n\mid 10000!$$ Obviously, we can see that there are fewer ...
2
votes
1answer
69 views

why $x^3=11^3$ mod $5083$ has only one solution?

Why $x^3=11^3$ mod $5083$ has only one solution? (The only answer is $x=11$) I know it has at most 3 roots but how to find that there isn't another answer?
5
votes
1answer
120 views

Prove that $\sqrt[3]{p}$, $\sqrt[3]{q}$ and $\sqrt[3]{r}$ cannot be in the same arithmetic progression

My cousin (he doesn't speak English well so I am writing on his behalf) is trying to do the following problem: Let $p$,$q$, $r$ be different primes (let's assume $p<q<r$). Show that ...
5
votes
2answers
505 views

Proving Inequality with the Greatest Integer Function

Show that $$[(m+n)x]+[(m+n)y] \ge [mx+(n-1)y]+[my+(n-1)x]$$ where $m,~n \in \Bbb{N}$ and $0\le x,~y < 1$. I've tried everything for about half a day and still couldn't figure it out. ...
1
vote
1answer
62 views

Prove that for $n\ge1$, $\xi-\frac{h_n}{k_n}=(-1)^nk_n^{-2}\left(\xi_{n+1}+\langle 0,a_n,a_{n-1},…,a_2,a_1\rangle\right)^{-1}$

Prove that for $n\ge1$, $$\xi-\frac{h_n}{k_n}=(-1)^nk_n^{-2}\left(\xi_{n+1}+\langle 0,a_n,a_{n-1},...,a_2,a_1\rangle\right)^{-1}$$ In addition, show that ...
2
votes
0answers
33 views

Any primitive root modulo $p^m$ is also a primitive root modulo $p$ [duplicate]

This is the last of the stream of number theory problems I have been looking at that I would like to discuss. Let $p$ be an odd prime number and let $m$ be a positive integer. Prove that any ...
1
vote
1answer
47 views

Prove that if $2^{4\times5^k}=x\times5^{k+3}+a,0<a<5^{k+3},$ then $5\mid x$

Let $$2^{4\times5^k}\equiv a \pmod {5^{k+3}},\\2^{4\times5^k}\equiv b \pmod {5^{k+4}},$$ and $0<a<5^{k+3},0<b<5^{k+4},$ prove that $a=b.$$(k>1)$ This is equivalent to this: if ...
3
votes
3answers
61 views

Prove that $\sum_{c \mid d} f(c) = d$

The following problem is the beginning of an easy proof using Möbius inversion to prove that if $p$ is a prime, then there are exactly $\phi(d)$ incongruent integers having order $d$ modulo $p$. Let ...
-1
votes
1answer
99 views

Proof involving indices of integers

Prove that $$\operatorname{ind}_gab\equiv \operatorname{ind}_ga + \operatorname{ind}_gb\pmod{p-1} $$ Where $$g^t \equiv k\pmod p \text{ if and only if } t \equiv \operatorname{ind}_gk \pmod{p-1}$$ ...
4
votes
0answers
66 views

Why has $3^x+4^y=5^z$ has only one solution (2,2,2) in positive integers? [duplicate]

First, do we have to exclude the cases, where $(x,y,z)$ are not all even or odd and then show the only possibility ? or is there a geometric solution maybe ?
0
votes
1answer
83 views

Finding positive integer solutions to $3^x + 55=y^2$

I think it must be finite, $y$ is always even, but I don't know how to continue. edit: with $x,y\in\mathbb Z$