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

learn more… | top users | synonyms

1
vote
1answer
97 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
448 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
477 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
303 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
847 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
63 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
47 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
324 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 ...
4
votes
2answers
312 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
211 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 ...
11
votes
2answers
330 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
305 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
170 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
413 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
4k 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
468 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
301 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
477 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
100 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
144 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
1k 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
489 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
586 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
567 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 ...
0
votes
1answer
603 views

How to arranged two or more different colored blocks in all possible ways?

Is any algorythem that can arrange two or more different blocks in all possible ways.. in series (rows and columns.)? If I have two colored(red and blue) blocks and I try to arranged in one possible ...
0
votes
1answer
105 views

A question on primitive roots

Let $p$ be an odd prime. How can Ihow that $a$ is a primitive root modulo $p$ iff $a^{(p-1)/q}\ncong 1 \pmod{p}$ for all prime divisors $q$ of $p-1$. Thanks
3
votes
4answers
643 views

Prove that $n=2^k -1$ is not a prime number, with $k=ab$. (Edit: $a\not=1$ and $b\not=1$)

My initial idea is to prove that $2^k-1$ can be written with at least two factors. My feeling is that having $k=ab$ helps with the factorization. But I don't know how to go from there.
2
votes
3answers
945 views

Hofstadter's TNT: b is a power of 2 - is my formula doing what it is supposed to?

If you've read Hofstadter's Gödel, Escher, Bach, you must have come across the problem of expressing 'b is a power of 2' in Typographical Number Theory. An alternative way to say this is that every ...
0
votes
2answers
103 views

Prime numbers: How would you do this efficiently?

Which of the following integers is prime: 187, 287, 387, 487, or 587? I can calculate it by hand, but that would take a long time. Is there an easier way? I noticed the numbers only differ 100 from ...
1
vote
0answers
100 views

Polygonal numbers modulo odd primes

Marc Renault's masters thesis "Properties of the Fibonacci Sequence Under Various Moduli" is well known for its investigation of Fibonacci numbers with focus on the distribution of residues, peiods of ...
2
votes
1answer
164 views

Are there integers like $x$, $y$ and $z$ that $6x+9y+15z=107$?

I have no idea what to do about this question: Are there integers like $x$, $y$ and $z$ that $$6x+9y+15z=107$$
2
votes
3answers
203 views

Multiplicative Order of $b \pmod p$ , where $p \equiv 1 \pmod 4$

Conjecture : Let $p$ be a prime number such that : $p \equiv 1 \pmod 4$ If multiplicative order of : $b \pmod p$ is $p-1$ then multiplicative order of : $(p-b) \pmod p$ is $p-1$ . ...
0
votes
2answers
156 views

Proof of existence quotient and remainder in $\mathbb Z$

Suppose $a = qb + r$, for $a,q,b,r \in \mathbb{Z}$ and $0 \le |r|<|b|$, $|b| > 0$, then $q$ is called the quotient and $r$ the remainder. Is the following proof of the existence of $q$ and $r$ ...
4
votes
2answers
161 views

Find all integers $k>2$ such that $5\equiv k \bmod k^2$

Find all integers $k>2$ such that $5\equiv k \bmod k^2$. I ended up with quardratic formula. Is it right?
1
vote
3answers
335 views

Euclidean Algorithm Problem

Given two cups holding 16oz. and 25oz. and enough water, how can you measure out exactly 3 oz. of water? It is easy to get $3=8\times16-5\times25$. But after thinking for a long time, I still ...
0
votes
2answers
622 views

Proof that there are infinitely many Ulam numbers

This is part of self-study; this question is taken from "Discrete Mathematics and Its Applications" (Rosen). We define the Ulam numbers by setting $u_1$ = 1 and $u_2$ = 2. Furthermore, after ...
2
votes
1answer
254 views

Expression that hits integer multiples of two variables

Is there a way to generate am expression that will get all integer multiples of an arbitrary pair of integers? I.e. Some function that will spit out ${0,2,3,4,6,8,9,10, ... }$ and all of the other ...
4
votes
3answers
125 views

If $m,n \in \mathbb{N}$ and $m> n$ then $(a^{2^{n}}+1)|(a^{2^{m}}-1)$ [duplicate]

Possible Duplicate: How to show $a^{2^n}+1 \mid a^{2^m}-1$? I am trying to solve the following question: If $m,n \in \mathbb{N}$ and $m> n$ then $(a^{2^{n}}+1)|(a^{2^{m}}-1)$, but I ...
12
votes
0answers
597 views

Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$?

Edward Waring, asks whether for every natural number $n$ there exists an associated positive integer s such that every natural number is the sum of at most $s$ $k$th powers of natural numbers ...
3
votes
2answers
187 views

Showing $24|(n+1)\implies24|\sigma_0(n)$

Question: Show that if $n$ is a positive integer such that $24$ divides into $n + 1$, then $24$ divides the sum of all divisors of $n$ (denoted in number theory by $\sigma_0(n)$). For example ...
13
votes
1answer
543 views

My attempt to prove GCD exists

Please review my attempt to prove a theorem. Any mistakes you point would be highly appreciated by me. To prove the theorem, I'll be using the following properties which I'm assuming have already ...
10
votes
2answers
420 views

Is the set of all numbers which divide a specific function of their prime factors, infinite?

Consider a number $n$ with prime factorization $n=p_1^{k_1} \cdot p_2^{k_2} \dots \cdot p_z^{k_z}$. We define a function $f(n)$ to be $f(n)=(p_1^{k_1+1}-1) \cdot (p_2 ^{k_2 +1}-1) \dots \cdot ...
3
votes
0answers
171 views

$GF(n,20)$ is prime iff : $GF(n,20) \mid S_{4^{n-1}}$?

Let us define recurrence equation as : $S_n=S_{n-1}^{10}-10\cdot S^8_{n-1}+35\cdot S^6_{n-1}-50\cdot S^4_{n-1}+25\cdot S^2_{n-1}-2$ , with $S_0=12$ and let us define following notation : ...
9
votes
4answers
3k views

Greatest prime factor of $n$ is less than square root of $n$, proof

I remember reading this somewhere but I cannot locate the proof.
65
votes
5answers
9k views

What is special about the numbers 9801, 998001, 99980001 ..?

Just saw this post, and realized that 1/9801 = ...
0
votes
1answer
140 views

$GF(n,6)$ is prime iff : $GF(n,6) \mid S_n$?

Let us define recurrence equation as : $S_n=S^3_{n-1}-3\cdot S_{n-1}$ , with $S_0=52$ and let us define following notation : $GF(n,6)=6^{2^n}+1$ I have noticed that : $GF(1,6) ...
7
votes
3answers
1k views

Infinite number of composite pairs $(6n + 1), (6n -1)$

I came across a problem in Dudley's Elementary Number Theory. Part (a) is to find one $n$ such that both $6n+1$ and $6n-1$ are composite. So I stumbled across $n=50$, which gives $299=13 \cdot 23$, ...
1
vote
1answer
537 views

Showing $p$ divides $(p-2)!-1$ when $p$ is prime

How might one show that $p$ divides $(p-2)!-1$ where $p$ is a prime number? I am not even sure if it is true but I have been randomly trying it on some primes and it seems to be true.
3
votes
5answers
3k views

How can one prove that the cube root of 9 is irrational?

Of course, if you plug the cube root of 9 into a calculator, you get an endless stream of digits. However, how does one prove this on paper?