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

learn more… | top users | synonyms

1
vote
3answers
361 views

Solving modular equations

Is there a procedure to solve this or is it strictly by trial and error? $5^x \equiv 5^y \pmod {39}$ where $y > x$. Thanks.
1
vote
2answers
94 views

Let $d=(a,b)$, $b=\beta d$ and $n>1$. If $\beta$ is odd number, prove that $(n^a+1,n^b-1)\le 2$.

Problem. Let $d=(a,b)$, $b=\beta d$ and $n>1$. If $\beta$ is odd number, prove that $(n^a+1,n^b-1)\le 2$. Solution (from the book). Each common divisor of numbers $n^a+1$ and $n^b-1$ has to be ...
-1
votes
1answer
180 views

Demonstration of a divisibility rule

A friend of mine who's studying mathematics challenged me to demonstrate that: For given integer numbers $n$ and $m$, we can say $$\left(\prod_{i=n}^m i\right)/{(m-n)!} =Z,$$ where $Z$ is some ...
2
votes
0answers
211 views

Primality test for Generalized Fermat numbers using Chebyshev polynomials of the first kind?

One can prove following statements : $A)$ Let's define sequence $S_i$ as : $S_i = \begin{cases} 2, & \text{if }i = 0 \\ 2S^2_{i-1}-1, & \text{otherwise} \end{cases}$ $ M_p = ...
3
votes
1answer
299 views

Amicable Pairs (How many have been found so far?)

My question is simply, how many amicable pairs have been found so far using super computers? I have been trying to find any kind of answer online that is up to date, but after searching in depth I ...
-4
votes
2answers
290 views

Find the last digit of this series, for any value of $n$ and $m$,

Find the last digit of this number: $$({}_{4n+1} C_0 )^{4m+1} + ({}_{4n+1} C_1 )^{4m+1} +({}_{4n+1} C_2 )^{4m+1} + \cdots + ({}_{4n+1} C_{4n+1} )^{4m+1}\;,$$ where $n$, $m$ belong to the holy set of ...
8
votes
3answers
3k views

Find The Last 3 digits of the number $2003^{2002^{2001}}$

Find The Last 3 digits of the number $2003^{2002^{2001}}$ BY number theory or otherwise, Also i would like to ask is there a property observed in the numbers of the form $k^n$, where for some $k, ...
1
vote
1answer
157 views

How to prove $\mathbb{Q}(\sqrt{2})$, as a real quadratic number field, possesses order.

I am new to number theory. My question is asking me to prove that $X:=\mathbb{Q}(\sqrt{2})$ is an ordered field that does not follow the Completion Axiom. I started by showing $X$ was a subring of ...
4
votes
2answers
182 views

A game of numbers: When can we have 2011?

Two friends are playing a game. In every turn, after one of them says a number $k$, the other one has to say a number in form $a\cdot b$ where $a,b\in \mathbb{N}$ such that $a+b=k$ holds. The game ...
13
votes
8answers
835 views

Approximation of $e$ using $\pi$ and $\phi$?

$$e \approx \frac{4 \phi +3 \pi-5}{4}$$ where $~\phi~$ is a Golden ratio . Is it possible to construct better approximation of $e$ using $\pi$ , $\phi$ and integers ?
1
vote
5answers
810 views

Number of pairs $(a, b)$ with $gcd(a, b) = 1$

Given $n\geq1$, how can I count the number of pairs $(a,b)$, $0\leq a,b \leq n$ such that $gcd(a,b)=1$? I think the answer is $2\sum_{i}^{n}\phi(i)$. Am I right?
1
vote
0answers
265 views

Primes p such that $3$ is a primitive root modulo $p$ , where $p=2^a \cdot M_q+1$

Let's define prime number $~p~$ as : $p=2^a \cdot M_q+1$ where $~M_q~$ is a Mersenne prime number such that $q \geq 3$ and $a$ is an even integer . Note that : Since $~M_q \equiv 1 \pmod 6 ...
3
votes
4answers
458 views

If $p$ is a prime, how many elements of $\{1, \ldots,( p^n) − 1\}$ have an inverse modulo $p^n$?

Question: If $p$ is a prime, how many elements of $\{1, \ldots , (p^n) − 1\}$ have an inverse modulo $p^n$? I've been mulling this problem over for days, and I still have absolutely no idea what it ...
14
votes
6answers
618 views

Calculate the 146th digit after the decimal point of $ \frac{1}{293} $

The question is: Calculate the 146th digit after the decimal point of $\frac{1}{293}$ 1 / 293 = 0,00341296928.., so e.g., the fifth digit is a 1. We know that 293 is a prime, probably this would ...
-3
votes
1answer
175 views

n -tuples of pythagorean

Respected all Mathematicians! As we know that n-tuple is a set of n positive integers ($a_1$,...$a_n$) such that sum of the squares of this each member up to a_n-1 is square of $a_n$. If we have ...
1
vote
1answer
67 views

Proof using GCD

Assume all variables are integers greater than 1. Suppose $y = k x$ and $k \neq x$. Suppose that $z\lt k$ and $\gcd(k, z) \gt 1$. Does this imply $\gcd(z, x) \lt x$?
3
votes
0answers
187 views

Sophie Germain Star prime number

Let us define following prime number : Let $~S_p~$ be Sophie Germain Star prime number of the form : $S_p=12\cdot p \cdot (2p+1)+1$ where $~p~$ is a Sophie Germain prime number . Note ...
2
votes
2answers
251 views

Given that $[n(n+1)(n+2)]^2 = 303916253\square96$, find the value of $\square$.

Given that $[n(n+1)(n+2)]^2 = 303916253\square96$, find the value of $\square$. Given that $[n(n+1)(n+2)]^2 = 30391625\square796$, find the value of $\square$. Problem Given that $[n(n+1)(n+2)]^2 = ...
10
votes
1answer
153 views

Constructing numbers from basic arithmetic on digits

I was tooling around over on stackoverflow and happened upon this question. To summarise, given the set of digits $\{1,2,3,4,5,6,7,8,9\}$ and a set of basic arithmetic (binary) operators ...
2
votes
2answers
166 views

Generalization of Pythagorean triples

Is it known whether for any natural number $n$, I can find (infinitely many?) nontrivial integer tuples $$(x_0,\ldots,x_n)$$ such that $$x_0^n + \cdots + x_{n-1}^n = x_n^n?$$ Obviously this is true ...
0
votes
1answer
58 views

Primes $K_n(b)$ such that $5$ is primitive root $\bmod {K_n(b)}$ , where $K_n(b)$ is generalized Kynea prime

How to prove or disprove following statement : Let $K_n(b)$ be generalized Kynea prime of the form : $K_n(b)=(b^n+1)^2-2$ , where : $b=2^k\cdot 3^l , ~k,l \in \mathbb{Z^{*}}$ then If $~n ...
4
votes
3answers
212 views

infinite subset in real plane and straight line

Let $A\subset\mathbb{R}^2$ be an infinite set such that the distance between any points $a,b \in A$ is an integer. Prove that A is a subset of a straight line. For any finite n, give an example of a ...
5
votes
1answer
1k views

Where is the problem in this proposed elementary proof of Fermat's Last Theorem [closed]

I stumbled across a website by a chap called Tom Ballard in which he presents his proof of FLT based on elementary techniques: http://www.fermatproof.com The style is rather 'non-standard', shall we ...
2
votes
1answer
816 views

All positive integers m,n such that $an+b=cm$?

Given positive integers a,b,c, how to find all positive integers m,n such that $an+b=cm$? Is there always infinitely many m,n for all a,b,c? If $(n_0, m_0)$ is the smallest solution, are all other ...
1
vote
3answers
99 views

Proof of relative primality

How is it true that: If $a_1, a_2,\ldots,a_n$ are pairwise relatively prime positive integers, then $M_i = \dfrac{(a_1a_2\cdots a_n)}{a_i} $ is relatively prime to $a_i$ ? This is ...
1
vote
1answer
96 views

How to find $(a,n)$ such that : $5^a+1 \equiv 0 \pmod {3\cdot 2^n-1}$ and $3\cdot 2^{n-1}-1 \equiv 0 \pmod a$?

Is it possible to find such integer pair $(a,n)$ that : $\begin{cases} 5^a+1 \equiv 0 \pmod {3\cdot 2^n-1} \\ 3\cdot 2^{n-1}-1 \equiv 0 \pmod a\\ \end{cases}$ where $n \equiv 3 \pmod 4$
5
votes
1answer
423 views

An approximate relationship between the totient function and sum of divisors

I was playing around with a few of the number theory functions in Mathematica when I found an interesting relationship between some of them. Below I have plotted points with coordinates ...
3
votes
2answers
468 views

Primes $p$ such that $5$ is primitive root $\bmod{p}$ , where $p$ is a $321$ prime

How to prove following statement : Let $~p~$ be Thabit $(321)$ prime of the form : $p=3\cdot 2 ^n-1$ and let $~n~$ be an odd number then : $~5~$ is a primitive root modulo $~p~$ iff $~n ...
12
votes
1answer
300 views

$a^m+k=b^n$ Finite or infinite solutions?

Given positive integers k,a,b, is there a finite or infinite number of solutions in positive integers $m,n>1$, to $a^m+k=b^n$? Pillai's conjecture states that each positive integer occurs only ...
3
votes
3answers
694 views

Dedekind cut of an irrational number

I have looked around at the questions about Dedekind cuts and still have some questions. For example, 1) Why is $\{r \in \mathbb{Q}: r^2 < 2 \}$ not a Dedekind cut and yet $\big( 0^{\ast}:=\{r ...
1
vote
1answer
60 views

Do all carmichael numbers contain a 1 or a 6?

I have only seen a short list but they all contain a 1 or a 6 somewhere.
0
votes
0answers
45 views

Solving the equation $n(n-1)\cdot\cdot\cdot(n-k+2)(n-k+1) = a$ [duplicate]

Possible Duplicate: How to reverse the $n$ choose $k$ formula? I want to calculate reverse binomial coefficients. Given a number $m$, I want to compute all possibilites how $m$ could be ...
3
votes
2answers
291 views

Can an element be a quadratic residue and a generator (mod p)?

i.e. is is possible for $g$ to be a generator$\mod{p}$, and $g \equiv x^2 \mod{p}$ for some $x$ I'm guessing not, as I think $x$ can't be expressed as a power of $g$, contradicting g being a ...
3
votes
2answers
308 views

puzzle about array of numbers

Consider an array of numbers $$ \color{#C00000}{1}\ \hphantom{7\ 6\ 5\ 4\ 7\ 3\ 5\ 7\ 2\ 7\ 5\ 3\ 7\ 4\ 5\ 6\ 7\ }\color{#C00000}{1}\\ 1\ \hphantom{7\ 6\ 5\ 4\ 7\ 3\ 5\ 7\ }\color{#C00000}{2}\ ...
7
votes
2answers
210 views

Inductive proof that $(m!^n)n! \mid (mn)!$

I have worked this problem out before but am stuck on the inductive step. Show that $(m!^n)n! \mid (mn)!$ I am using induction on $n$. I thought to factor $(m(n+1))$! but can't get it ...
10
votes
2answers
312 views

Finding all the numbers that fit $x! + y! = z!$

I have the formula $x! + y! = z!$ and I'm looking for positive integers that make it true. Upon inspection it seems that x = y = 1 and z = 2 is the only solution. The problem is how to show it. ...
1
vote
1answer
278 views

about Pythagorean quadruples

Respected Mathematicians, I would like to prepare a function, which will generate Pythagorean quadruples (a, b, c, d) = $d^2$ = $a^2$ + $b^2$ + $c^2$...-> (1). How far I am correct I don't know. For ...
3
votes
0answers
167 views

Primes $p$ such that $3$ is a Primitive Root Modulo $p$

In this paper (Proposition 4) you can find statement : If $p$ is a prime of the form : $p = 2q + 1$ for some odd prime $q$, then $2$ is a primitive root modulo $p$ if and only if : $q \equiv ...
3
votes
1answer
407 views

Help in understanding the properties of prime numbers

I was reading about hashing. The oldest/standard approach is to use a prime number to produce the hash. At first I couldn't get why use a prime when I came to this Why hash functions use primes: ...
7
votes
4answers
3k views

equilateral triangle with integer coordinates

Is it possible to construct an equilateral triangle with coordinates on a grid of integers? I think the answer is no, but how can I prove this? I started with a triangle with coordinates (0,0) (a,b) ...
1
vote
2answers
458 views

Primitive roots modulo $~p~$, where $~p\equiv 1 \pmod 4 ~$?

I would like to propose generalization of this question : Let $p$ be a prime number such that : $p\equiv 1 \pmod 4$ Show that $~k\cdot p \pm a~$ is a primitive root modulo $p~$ iff $a$ ...
5
votes
3answers
299 views

Basic question on primitive roots

From Ireland and Rosen's A Classical Introduction to Modern Number Theory, p.48: Let $p$ be a prime of the form $4t+1$. Show that $a$ is a primitive root $\bmod p$ iff $-a$ is a primitive root ...
3
votes
3answers
452 views

A better approximation of $H_n $

I'm convinced that $$H_n \approx\log(n+\gamma) +\gamma$$ is a better approximation of the $n$-th harmonic number than the classical $$H_n \approx \log(n) +\gamma$$ Specially for small values of $n$. ...
2
votes
2answers
97 views

Congruence question

Hi I would like a hint with the following congruence question. $$1+x^{1}+x^{2}+\cdots +x^{6}\equiv 0\mod{29}$$ Is there a formula I should be looking for to group the left hand side?
2
votes
1answer
140 views

Is $17$ primitive root modulo $F_n(6)$?

Is it true that : $17$ is primitive root modulo $F_n(6)$ where $F_n(6)$ is generalized Fermat prime of the form: $F_n(6) =6^{2^n}+1 , ~~ n \geq 0$ I know that one can use quadratic ...
2
votes
5answers
910 views

show if $n=4k+3$ is a prime and ${a^2+b^2} \equiv 0 \pmod n$ , then $a \equiv b \equiv 0 \pmod n$

$n = 4k + 3 $ We start by letting $a \not\equiv 0\pmod n$ $\Rightarrow$ $a \equiv k\pmod n$ . $\Rightarrow$ $a^{4k+2} \equiv 1\pmod n$ Now, I know that the contradiction will arrive from the fact ...
3
votes
1answer
393 views

Number of solutions of $x^2=1$ in $\mathbb{Z}/n\mathbb{Z}$

Next is what I have worked out to the moment. $1$ and $-1$ are roots for all $n$. $x \in \mathbb{Z}/n\mathbb{Z},\ $ $x^2\equiv1 \Leftrightarrow (x-1)(x+1)\equiv0 \Leftrightarrow \exists k \in ...
4
votes
1answer
1k views

Bounds of Euler's totient function?

Conjecture : Let $\phi(m)$ be Euler's totient function $1 \leq \phi(m) \leq \lceil \frac{m-1}{2} \rceil ~~$ if $~~m~~$ is even $\lceil \frac{m+1}{3} \rceil \leq\phi(m) \leq m-1 ~~$ ...
0
votes
2answers
523 views

Proving properties of modular arithmetic by induction

I am trying to prove a property of modular arithmetic, namely: $$[(a\bmod n)\times (b\bmod n)]\bmod n = ab\bmod n.$$ I have the basis and hypothesis steps down, but I am having trouble with the ...
5
votes
2answers
526 views

Infinite quantity of primes of the form $4k+1$

I need to prove that there are infinitely many primes of the form $4k+1$. I have proved that $-1$ is not a quadratic residue modulo $4k-1$ and is a quadratic residue modulo $4k+1$. Thus I need to ...