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

learn more… | top users | synonyms

3
votes
2answers
96 views

How can “ $\small {n \over \varphi(n) } \text{ is integer only if } n=2^r \cdot 3^s $ ” simply be shown?

I've tried to answer the question concerning $\small { 3^n-2^n\over n } $ and wanted to show this simply by referring to the property that $$ 3^{\varphi (n)}-2^{\varphi (n)}\equiv 0 \pmod n $$ ...
3
votes
2answers
4k views

Congruence Modulo with large exponents

How will the congruence modulo works for large exponents? What theorem/s may be used? For example to show that $7^{82}$ is congruent to $9 \pmod {40}$.
1
vote
3answers
99 views

Some doubt on Linear Diophantine equation

We know $ax+by=c$ is solvable iff $(a,b)|c$ where $a,b,c,x,y$ are integers. If $x=2$, $a=\dfrac{k(k+5)}{2}$, $y=k$, $b=k+3$ and $c=2k$, where $k$ is any integer, then $$2 \frac{k(k+5)}{2} - k(k+3) = ...
1
vote
1answer
99 views

Is $\frac{\sigma(q^k)}{\sigma(n^2)}$ bounded from below by a function of $n$, if $q \equiv 1 \pmod 4$ is prime and $n^2$ is deficient?

If $q$ is a prime with $q \equiv k \equiv 1 \pmod 4$ and $n^2$ is deficient, is $\frac{\sigma(q^k)}{\sigma(n^2)}$ bounded from below by a function of $n$? Of course, an easy lower bound is ...
2
votes
1answer
93 views

What is the characteristic of a projective plane?

Let $p \in \mathbb{N}$ be a prime number and $E$ the projective plane induced by the one and two dimensional linear subspaces of $(\mathbb{F}_p)^3$. I shall prove, that the characteristic of $E$ is ...
5
votes
2answers
223 views

Is there any number in $\mathbb Z[\sqrt{5}]$ with norm equals 2?

Is there any number $a+b\sqrt{5}$ with $a,b \in \mathbb{Z}$ with norm (defined by $|a^2−5b^2|$) equal 2?
2
votes
1answer
146 views

Find numbers with a given number of divisors.

There was a final school exam in Russia recently, "Unified State Exam", that has the following problem in it's most complex chapter, "C": C6: Find all numbers that end with "$0$" (decimal notation, ...
4
votes
0answers
279 views

Sum of floor function $\pmod{n}$

Let $n$ be a positive integer. Let $a$ be a nonzero integer such that $\gcd(a,n)=1$. How to show that $$\frac{a^{\phi (n)}-1}{n} \equiv \sum_i \frac{1}{ai} \left \lfloor \frac{ai}{n} \right \rfloor ...
2
votes
4answers
355 views

All odd primes except $5$ divide a number made up of all $1$s

Okay, so I have worked on this problem and even though I can see it is true I just don't know how to show it. Here it goes. Question: Show that every odd prime except $5$ divides some number of the ...
7
votes
3answers
329 views

Which number was removed from the first $n$ naturals?

A number is removed from the set of integers from $1$ to $n$. Now, the average of remaining numbers turns out to be $40.75$. Which integer was removed? By some brute force, I got $61$. I want to know ...
1
vote
3answers
2k views

Smallest multiple whose digits are only ones and zeros [duplicate]

I have a collection of typewritten pages that formed the basis of a third year problem solving course offered about 25 years ago at U. Waterloo. I've been slowly working through the problems and have ...
1
vote
3answers
308 views

Is $3^n - 2^n$ composite for all integers $n \geq 6$?

I made a conjecture about the values of n for which $3^n - 2^n$ is not prime, but I didn't succeed in proving the conjecture. My conjecture is the following: "Suppose n is an integer greater than or ...
13
votes
5answers
3k views

If $n$ is composite, then $n$ divides $(n-1)!$.

I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
1
vote
2answers
255 views

How to prove an integer is (not) a power of some other integer?

I assume that is nigh-impossible to prove when the conditions on the integers are very general. However, my algebra professor told me that the following is true: If $n$ is a composite positive ...
4
votes
3answers
909 views

Some digit summation problems

What is the sum of the digits of all numbers from 1 to 1000000? In general, what is the sum of all digits between 1 and N? f(n) is a function counting all the ones that show up in 1, 2, 3, ...
0
votes
4answers
398 views

For prime $p>2: 1^23^25^2\cdot\cdot\cdot(p-2)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p$ [duplicate]

Possible Duplicate: Why is the square of all odds less than an odd prime $p$ congruent to $(-1)^{(p+1)/(2)}\pmod p$? If p is an odd prime, prove that $1^2 \times 3^2 \times 5^2 \cdots \times ...
1
vote
1answer
373 views

Sum of prime powers equal to a prime power

Considering the equation $p^{k+1}-1=(p-1)q^n$, where $p$ and $q$ are primes, $k$ and $n$ are integers such that $k>1$ and $n>0$, is it true that $p<q$? Thanks in advance. Edit: it can be ...
2
votes
1answer
108 views

Is there a pattern for reducing exponentiation to sigma sums?

The other day I was trying to find a method for cubing numbers similar to one I found for squaring numbers. I found that to find the square of a positive integer n, just sum up the first n odd ...
2
votes
2answers
106 views

Largest modulus for Fermat-type polynomial

Motivated by this question, I wonder: Given $k\in\mathbb N, k\ge2$, what is the largest $m\in\mathbb N$ such that $n^k - n$ is divisible by $m$ for all $n\in\mathbb Z$ ?
4
votes
2answers
428 views

The arithmetic progression $ a, a+b, a+2b, a+3b,\dots $ has $k$ consecutive composites

For any $k>0$, prove that the arithmetic progression $$ a, a+b, a+2b, a+3b, \dots$$ where $\gcd(a,b)=1$ contains $k$ consecutive terms which are composite. If it's for all $a,b$ then I'm ...
7
votes
4answers
1k views

Proof of irrationality of square roots without the fundamental theorem of arithmetic

Here is an elementary proof (adapted from Hardy's A Course of Pure Mathematics) that for any integer $k$, $\sqrt{k}$ is either irrational or integral. Suppose $\sqrt{k}$ is rational, $\sqrt{k} = ...
3
votes
2answers
88 views

For how many integral values of $R$ is $R^4 - 20R^2+ 4$ a prime number?

For how many integral values of $R$ is $R^4 - 20R^2+ 4$ a prime number? I tried factorizing but couldn't conclude anything concrete. Factorizing it, gives $(R^2 - 10)^2 - 96$. What should be my ...
8
votes
1answer
128 views

Summing over a cyclic subgroup of a multiplicative group mod n

Let $x$ be a unit in $\mathbb Z/ n \mathbb Z$ of multiplicative order $m$. I am trying to determine when it is that $$ \sum_{i=0}^{m-1} x^i \equiv 0 \mod n . $$ Is this kind of situation something ...
5
votes
3answers
391 views

finding the rational number which the continued fraction $[1;1,2,1,1,2,\ldots]$ represents

I'd really love your help with finding the rational number which the continued fraction $[1;1,2,1,1,2,\ldots]$ represents. With the recursion for continued fraction $( p_0=a_0, q_0=1, p_{-1}=1, ...
7
votes
6answers
389 views

What are the subsemigroups of $(\mathbb N,+)?$

While trying to solve a somewhat bigger problem, I realized that I don't know what the subsemigroups of one of the most important semigroups, $(\mathbb N,+)$, are. (I assume $0\not\in\mathbb N$.) I've ...
4
votes
1answer
125 views

Which person will leave in last?

Can anyone give me the quickest idea to solve the question below? Read the information below and answer the question that follows. In a mathematical game, one hundred people are standing in a ...
3
votes
2answers
184 views

deciding whether $125$ is a primitive root modulo $529$

I'd like your help with the following: I need to show that $5$ is a primitive root modulo $23^m$ for all natural $m$ and to decide if $125$ is a primitive root modulo $529$. For the first part I need ...
7
votes
1answer
192 views

Flirtatious Primes

Here's a possibly interesting prime puzzle. Call a prime $p$ flirtatious if the sum of its digits is also prime. Are there finitely many flirtatious primes, or infinitely many?
1
vote
3answers
124 views

Smallest number in a set

A is the set of seven consequtive two digit numbers, none of these being multiple of 10. Reversing the numbers in set A forms numbers in set B. The difference between the sum of elements in set A ...
4
votes
2answers
143 views

for every prime $p>7$, there are integers $x,y$ such that $p=x^2+7y^2$, if and only if, $p \equiv 1,2,4 \pmod7$.

I'd really love your help with showing that for every prime $p>7$, there are integers $x,y$ such that $p=x^2+7y^2$, if and only if, $p \equiv 1,2,4 \pmod7$. $x^2+7y^2$ is the norm of the Euclidean ...
16
votes
5answers
1k views

Prove that every number ending in a $3$ has a multiple which consists only of ones.

Prove that every number ending in a $3$ has a multiple which consists only of ones. Eg. $3$ has $111$, $13$ has $111111$. Also, is their any direct way (without repetitive multiplication and ...
4
votes
2answers
159 views

Solving $x^{18} \equiv 64 \pmod {13^2}$

I'm trying to solve $x^{18} \equiv 64 \pmod {13^2}$ and while trying I'm losing my mind. First question was to prove that $ 2$ is a primitive root for $13^n$ for all natural $n$, and then I had to ...
3
votes
0answers
259 views

Proof that $ 1^3+2^3+\cdots +n^3 = (1+2+\cdots+n)^2$ without using induction [duplicate]

Possible Duplicate: Intuitive explanation for the identity $\sum\limits_{k=1}^n {k^3} = \left(\sum\limits_{k=1}^n k\right)^2$ How to prove this without using mathematical induction? ...
7
votes
1answer
224 views

Multiplicative property of the GCD

I need to prove that $$(ah,bk)=(a,b)(h,k)\left( \frac{a}{(a,b)},\frac{k}{(h,k)}\right)\left( \frac{b}{(a,b)},\frac{h}{(h,k)}\right)$$ I'm most certain I need to use ...
2
votes
3answers
307 views

Single-digit even natural number solutions to the equation $a+b+c+d = 24$ such that $a+b > c+d$ [duplicate]

Possible Duplicate: Two algebra questions How to approach the below question: How many single-digit even natural number solutions are there for the equation $a+b+c+d = 24$ such that ...
4
votes
5answers
206 views

Property of $2^n+1=xy$

I was wondering if the following were true. It makes sense but I'm having trouble concocting any formal reasoning. Let $2^n+1=xy$ for some integers $x,y>1$ and $n>0$. For $a\in\mathbb{Z}^+$, ...
1
vote
4answers
7k views

Finding sum of factors of a number using prime factorization

Given a number, there is an algorithm described here to find it's sum and number of factors. For example, let us take the number $1225$ : It's factors are $1, 5, 7, 25, 35, 49, 175, 245, 1225 $ and ...
5
votes
7answers
226 views

Simplest method to find $5^{20}$ modulo $61$

What is the simplest method to go about finding the remainder of $5^{20}$ divided by $61$?
7
votes
1answer
343 views

A number has 101 composite factors.

A number has 101 composite factors. How many prime factors at max A number could have ?
0
votes
1answer
657 views

Sum of Absolute Values

I was going over a question and I wanted your opinion(s) on it: The product of two numbers is 6 and one of the numbers is 5 less than the other. What is the absolute value of the sum of the ...
7
votes
4answers
313 views

computing ${{27^{27}}^{27}}^{27}\pmod {10}$

I'm trying to compute the most right digit of ${{27^{27}}^{27}}^{27}$. I need to compute ${{27^{27}}^{27}}^{27}(\bmod 10)$. I now that ${{(27)^{27}}^{27}}^{27}(\bmod 10) \equiv{{(7)^{27}}^{27}}^{27} ...
2
votes
2answers
68 views

For prime $p$, $p\equiv 5 (\bmod 8)$, and $a$ such that $\left(\frac{a}{p}\right)=1$: $a^{\frac{p-1}{4}}$ is either $1$ or $-1$

I'd really love your help with the following problem: For prime $p$, $p= 5 (\bmod 8)$, and $a$ such that $(\frac{a}{p})=1$ (Legendre symbol): I need to show that $a^{(p-1)/4}$is either $1$ or $-1$ ...
1
vote
1answer
94 views

The congruence $f(x)=x^3+3x+9 \equiv 0 (\bmod 5^n)$ has only one solutions for every $n \geq 2$

I need to prove that the congruence $f(x)=x^3+3x+9 \equiv 0 (\bmod 5^n)$ has only one solutions for every $n \geq 2$. I checked with Hensel theorem that for $n=2$ there is one solution indeed. I ...
3
votes
4answers
1k views

Modular arithmetic for negative numbers

If I have the congruence $$m^2 \equiv -1 \pmod {2k+1}$$ how do I solve for the solutions to this congruence (given that I know $k$)?
2
votes
3answers
599 views

Finding all integer solutions for $x^2 - 2y^2 =2 $

I'd love your help with finding all the integer solutions to the following equation: $x^2 - 2y^2 =2 $. I want to use Pell's theorem so I changed the equation to $-\frac{1}{2}x^2+ y^2 =-1$, Can I use ...
7
votes
1answer
122 views

A proof in number theory dealing with modular congruences.

So we are asked to show that $$(p-1)(p-2)\cdots(p-r)\equiv (-1)^{r}r! \pmod{p}$$ for $r=1,2,...,p-1$. I worked on it and I want to know if my proof suffices to show what is being asked. I would also ...
1
vote
4answers
827 views

For $q, p$ odd primes such that $p \neq q$, there is not primitive root modulo $pq$.

I'd really love your help with proving that for $q, p$ odd primes such that $p \neq q$, there is not primitive root modulo $pq$. There's a theorem says that there's primitive root only for $2, 4, ...
1
vote
3answers
178 views

Need a “Prime Square” type of number (For my significant other)

No this isn't for a silly math exercise, it's a relationship with a hottie I don't want to lose at stake: I like my TV volume to be on Perfect Squares, but she likes her volumes on Prime Numbers. ...
1
vote
1answer
115 views

An elementary congruence question in number theory

If ${q^k}\sigma(q^k) \equiv a \pmod b$ and $\displaystyle\frac{\sigma(q^k)}{n} \neq \displaystyle\frac{\sigma(n)}{q^k}$, does it follow that $n\sigma(n) \not\equiv a \pmod b$? Here, $q$ is prime and ...
1
vote
2answers
96 views

$p(x) \mid q(x)$ for infinite values of $x$ (integer) implies $p(n) \mid q(n) \quad \forall n$ integer

I was working on: Kind of Functional Eq. in Integers I found a sort of way... but I need to show that: $p(x) \mid q(x)$ for infinite values of $x$ (integer) implies $p(n) \mid q(n) \quad \forall n ...