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

learn more… | top users | synonyms

3
votes
1answer
249 views

If $p - 1 = 2q$, and $5$ is a primitive root $\bmod q$, then $5$ is a primitive root $\bmod p$

Let $p$ and $q$ be odd primes. If $p - 1 = 2q$, and $5$ is a primitive root $\bmod q$, then $5$ is a primitive root $\bmod p$. Thanks to Álvaro Lozano-Robledo, here is what i have; valid? If: (A) p ...
4
votes
3answers
131 views

to find number of divisor of $p^m$ times $q^n$ when $p$ and $q$ are primes

Am taking a intro discrete math course..it covers some number theory content Euclidean algorithm,modular arithmetic, Euler's phi function, that's all How can I solve a question like this: If $p$ and ...
3
votes
3answers
188 views

How do I find triangular numbers $a$ and $b$ such that $a+b$ and $a-b$ are also triangular?

As a challenge problem in my number theory course I was asked to find the 2 pairs of triangular numbers $a$ and $b$ smaller than 1000 for which $a+b$ and $a-b$ are also triangular. For example 15 ...
0
votes
2answers
96 views

How many numbers end in the four digits 1995 and become an integer number of times smaller when these digits are erased?

How many numbers end in the four digits 1995 and become an integer number of times smaller when these digits are erased? I do not understand the question through but I think this is asking for all ...
1
vote
2answers
73 views

Which of the following is necessarily a divisor of the number $n\times1000+2 \times n$ where $n\lt 500$?

A three-digit number 'n' (less than 500) is taken. A six-digit number is formed by writing the number 'n' as first three digits and the number '2n' as the last three. Which of the following is ...
1
vote
0answers
80 views

An alternative way to test primality of Fermat numbers?

How to prove following statement : Let's define an infinite sequence of positive integers : $ a_i=\cos(4^{i} \cdot \arccos(4)) ; i=1,2,3......$ then for $n \geq 2 , F_n$ is prime if and ...
19
votes
5answers
10k views

Can decimal numbers be considered “even” or “odd”?

Is the concept of even/odd numbers is applicable to decimal numbers? For e.g. - 4.222 is a even number?
11
votes
2answers
282 views

Find all positive integers $n$ for which $(n-1)!+1$ is a power of $n$

As the title says, Find all positive integers $n$ for which $(n-1)!+1$ is a power of $n$. The solutions I've found are $\{2,3,5\}$ (thanks Brandon!), but I'm having difficulties proving that ...
1
vote
2answers
368 views

twin prime conjecture

Whether I am correct or wrong I don't know. If there are any corrections, please let me know. Let $p_n$ = product of all primes. (of course we can go still beyond as we know $p_n$ is infinite). Now ...
4
votes
3answers
684 views

How to prove $\gcd(m, n) = \gcd(-m, n)?$

Beginner question here: For a quiz on Elementary Number Theory in my Discrete Math course I was asked to prove if $\gcd(m, n) = \gcd(-m, n)$. I used the Euclidean Algorithm to show that the two ...
143
votes
2answers
13k views

Proving you *can't* make $2011$ out of $1,2,3,4$: nice twist on the usual

An undergraduate was telling me about a puzzle he'd found: the idea was to make $2011$ out of the numbers $1, 2, 3, 4, \ldots, n$ with the following rules/constraints: the numbers must stay in order, ...
3
votes
2answers
318 views

Number of nonnegative integral solutions of $x_1 + x_2 + \cdots + x_k = n$

To find all solutions greater than or equal to $1$ of a linear equation in the form $$x_1+x_2+x_3+\cdots+x_k=n ,$$ the number of them is $\binom{n-1}{k-1}$. If I need all solutions to be greater or ...
5
votes
1answer
137 views

Solving $a^n \equiv q \pmod{p}$ for $n$

Denote $a = 11114$, $p = 44449$, $q=21433$ and note that $p$ and $q$ are primes ($a$ isn't prime). I wish to find a natural number $n$ such that : $a^n \equiv q\mbox{ mod }p$. I tried to find such ...
1
vote
0answers
96 views

How do you find small coefficients that satisfy a particular modular equation

Let's say $p=16301$. How do I best find sets of small values for $a$, $b$ and $c$ for an equation like $$a p^3+b p^2+c p=11263 \mod\ 2^{16}.$$ I can use the ...
23
votes
9answers
5k views

Prove $2^{1/3}$ is irrational.

Please correct any mistakes in this proof and, if you're feeling inclined, please provide a better one where "better" is defined by whatever criteria you prefer. Assume $2^{1/2}$ is irrational. ...
0
votes
1answer
96 views

Notation for $f(n) = \frac{\Lambda(n)}{\log n}$?

Is there any sort of standard notation for the value represented by $f(n) = \frac{\Lambda(n)}{\log n}$, where $\Lambda(n)$ is the Mangoldt function? So essentially a function that is $\frac {1}{a}$ ...
6
votes
1answer
671 views

Implementing Fermat's Primality Test

I am trying to implement Fermat's primality test to test whether a given number n is prime or not. According to Wikipedia the test is as follows: Given an integer n, choose some integer a coprime ...
4
votes
1answer
343 views

How to prove that if a prime divides a Fermat Number then $p=k\cdot 2^{n+2}+1$?

If a prime $p$ divides a Fermat Number then $p=k\cdot 2^{n+2}+1$? Does anyone know a simple/elementary proof?
2
votes
1answer
167 views

Polynomial equations in $n$ and $\phi(n)$

If $n$ is a positive integer, let $\phi(n)$ the Euler function. ( if $n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$ with $p_i$ distinct primes, we have $\phi(n)=p_1^{\alpha_1-1} \dots ...
2
votes
1answer
109 views

Solving for the smallest $x$ : $1! + 2! + \cdots+ 20! \equiv x\pmod 7$

I know the smallest $x \in \mathbb{N}$, satisfying $1! + 2! + \cdots + 20! \equiv x\pmod7$ is $5$. I would like to know methods to get to the answer.
1
vote
1answer
194 views

Unique factorization less than 100

How do I approach this problem using unique factorization?... How many numbers are product of (exactly) $3$ distinct primes $< 100$? edit: Just to add to that, How does unique factorization ...
3
votes
1answer
207 views

Finding any digit (base 10) of a binary number $2^n$

I was doing some Math / CS work, and noticed a pattern in the last few digits of $2^n$. I was working in Python, in case anyone is wondering. The last digit is always one of 2, 4, 8, 6; and has a ...
4
votes
4answers
2k views

Difficulty in finding modulus of fraction

It is quite easy to evaluate $\frac{a}{b}\bmod m$ when $a$, $b$ and $m$ are integers and $\gcd(b,m)=1$ by replacing $\frac{1}{b}$ with an inverse of $b$ modulo $m$. But, is it possible to evaluate ...
13
votes
5answers
1k views

product of six consecutive integers being a perfect square

A 1939 paper of Erdos (Note on Products of Consecutive Integers, J. London Math. Soc. 14 (1939), 194–198) shows that a product of consecutive positive integers cannot be a perfect square. He ...
1
vote
2answers
755 views

How do you get possible candidates for primitive roots of 12?

Candidates for primitive roots are 1, 5, 7 and 11. $\phi(12)=\phi(2^2)\phi(3)=4$. $ord_{12}1 =1, ord_{12}5 =2, ord_{12}7 =2, ord_{12}11 =2$. None of these has $\phi(12)=4$, thus number 12 has ...
1
vote
2answers
187 views

Something like : “recursive” harmonic numbers? Where can I read more?

In my other thread I discussed a matrix-decomposition; for one matrix (U) I found now a description of its entries, which may best be denoted as "recursive harmonic numbers". However, googling with ...
4
votes
0answers
679 views

Solve Polynomial Congruence mod $89^2$

Solve $3x^2+6x+5\equiv 0\pmod{89^2}$. To do this, I first solved $3x^2+6x+5\equiv 0\pmod{89}$. This has a solution since $3x^2+6x+5 = 3(x+1)^2 + 2$ and $3(x+1)^2 \equiv -2 \pmod{89}$ has a ...
0
votes
1answer
166 views

A triangular array of numbers.

So I was given the triangular array of numbers below (the first line consists of two "1") $$11$$ $$1\frac{3}{2}1$$ $$1\frac{6}{4}\frac{6}{4}1$$ $$1\frac{10}{7}\frac{10}{6}\frac{10}{7}1$$ ...
1
vote
1answer
153 views

A rule to determine the crossed out digit

Lets take any integer, $z=abc\cdots$, form the sum of its digits, $a+b+c+\cdots$, subtract this from $z$, cross out any one digit from the result, and denote the sum of the remaining digits by $w$. ...
1
vote
1answer
59 views

Sequences of the form : $p_n=2^{p_{n-1}}-a$?

There is known Catalan sequence : $C_n=2^{C_{n-1}}-1$ , with $C_0=2$ I have noticed that following sequence produces prime numbers for the first four terms (I don't know if the fifth term is a prime ...
3
votes
3answers
144 views

Coefficient $\small c_{k} $ at $\small x^k$ in $\small (x-1)(x-1/2)(x-1/3)…(x-1/n) $?

This is a detail question from my current main question , but came out as a standalone problem. Background: I've found a description for the matrix T but to have this practically usable I need a ...
0
votes
0answers
47 views

For any prime $p \equiv 1\pmod{5}$ what integers $\{a_0, \dots, a_4\}$ satisfy $(\sum_{i=0}^{4}{a_ig^i})(\sum_{i=0}^{4}{a_ig^{-i}})=p^2$?

For any prime $p \equiv 1 \pmod{5}$ do there exist 5 integers $\{a_0, \dots, a_4\}$, each of absolute value less than $p$, satisfying $\sum_{i=0}^{4}{a_i}=p$, ...
1
vote
2answers
142 views

Compositeness of number $k\cdot 2^n+1$?

Every odd prime number can be expressed in the form $k \cdot 2^n+1$ ,where $k$ is an odd number . For $n>2$ number $k \cdot 2^n+1$ is composite if : $1.$ $k\equiv 1 \pmod {30} \land (n\equiv 2 ...
2
votes
1answer
190 views

How to go from Fermat’s little theorem to Euler’s theorem thought Ivory’s demonstration?

Ivory’s demonstration of Fermat’s theorem exploit the fact that given a prime $p$, all the numbers from $1$ to $p-1$ are relatively prime to $p$ (obvious since $p$ is prime). Ivory multiply them by x ...
3
votes
6answers
2k views

Trick to find multiples mentally

We all know how to recognize numbers that are multiple of $2, 3, 4, 5$ (and other). Some other divisors are a bit more difficult to spot. I am thinking about $7$. A few months ago, I heard a simple ...
3
votes
1answer
680 views

Are there infinitely many Mersenne primes?

known facts : $1.$ There are infinitely many Mersenne numbers : $M_p=2^p-1$ $2.$ Every Mersenne number greater than $7$ is of the form : $6k\cdot p +1$ , where $k$ is an odd number $3.$ ...
2
votes
1answer
120 views

Find and prove an upper bound on the number of intersections on two distinct polynomials

Find and prove an upper bound on the number of times that two distinct polynomials of degree $d$ can intersect. What if the polynomials' degrees differ? My attempt: let $p(x)$ and $q(x)$ be two ...
0
votes
3answers
82 views

Does $a \equiv b \pmod n$ mean $n \mid a - b$ or $n \mid b -a$

If I have $a \equiv b \pmod{n}$, it means $n \mid b - a$. But can you write it as $n \mid a - b$ as well?
0
votes
2answers
138 views

Prove a property of divisor function

Let $n$ be a positive natural number whose prime factorization is $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where $p_i$ are natural distinct prime numbers, and $a_i$ are positive natural numbers. ...
2
votes
1answer
139 views

How many integers less than $300$ is such that the sum of any two of them is not divisible by $3$?

Pam chose some numbers from $1$ to $300$ and wrote them down. As she observed her list, she noticed a peculiar fact that no two numbers on this list added up to a multiple of $3$. What can be ...
8
votes
1answer
1k views

Is there a way to find the first digits of a number?

Is there a way to find the first digits of a number? For example, the largest known prime is $2^{43,112,609}-1$, and I did sometime before a induction to find the first digit of a prime like that. ...
0
votes
3answers
67 views

Prove how many distinct elements in the set $\{ax \pmod{m}:a\in\{0,…,m-1\}\}$

There are $\dfrac{m}{\gcd(m,x)}$ distinct elements in the set $\{ax \pmod{m}:a\in\{0,...,m-1\}\}$ I have only known these by using a computer to generate the number of distinct elements. But I am not ...
3
votes
3answers
164 views

Prove for Fibonacci numbers: $3\mid f(n) \iff 4\mid n$

Let $f(n)$ be the $n$th Fibonacci number. Prove that $$3\mid f(n) \iff 4\mid n$$ I tried to use induction to prove it but I couldn't continue when I reached $n+1$ case.
2
votes
3answers
266 views

Prove or disprove an equation about Euler's $\phi$ function

Let $\phi(n)$ be the Euler's phi function and $p>q,m>1$, $\phi(m^p)>\phi(m^q)$ My intuition tells me this is true but I am not sure how to prove it. I know little about Euler's phi ...
4
votes
3answers
211 views

Find the remainder of $1234^{5678}\bmod 13$

Find the reminder of $1234^{5678}\bmod 13$ I have tried to use Euler's Theorem as well as the special case of it - Fermat's little theorem. But neither of them got me anywhere. Is there something ...
3
votes
3answers
157 views

Prove equations in modular arithmetic

Prove or disprove the following statement in modular arithmetic. If $a\equiv b \mod m$, then $ a^2\equiv b^2 \mod m$ If $a\equiv b \mod m$, then $a^2\equiv b^2 \mod m^2$ If $a^2\equiv b^2\mod m^2$, ...
10
votes
4answers
1k views

Prime Partition

A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
-1
votes
1answer
182 views

How to prove that $(\frac{n-b}{n}) =(\frac{n}{n})-(\frac{b}{n})$?

How to prove that $\displaystyle\left(\dfrac{n-b}{n}\right) =\left(\dfrac{n}{n}\right)-\left(\dfrac{b}{n}\right) $? What is $\displaystyle\left(\dfrac{n}{n}\right)$? Here, $\left(\dfrac{a}{b}\right)$ ...
0
votes
0answers
100 views

Is this probabilistic argument about “mutual primitive roots” correctly done?

A recent sci.math thread is called "mutual primitive roots". It is about quasi's conjecture that For each prime $q>2$, there is a prime $p<q$ such that $p$ is a primitive root of $q$, and ...
1
vote
2answers
60 views

How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?

How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?